两数之和

import java.util.HashMap;
public class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int n = numbers.length;
        int[] result = new int[2];
        //map里面放 键为target-每个数的结果 值为下标 
        //每次放入的时候看是否包含 当前值 
        //有的话说明当前值和已包含的值下标的那个元素为需要的结果
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        for(int i=0;i<n;i++){
            if(map.containsKey(numbers[i])){
                result[0] = map.get(numbers[i])+1;
                result[1] = i+1;
                break;
            }
            else{
                map.put(target - numbers[i], i);
            }
        }
        return result;
    }
}

此题和leetcode上有所不同，leetcode上下标已改为从0开始

import java.util.HashMap;
public class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer,Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(nums[i])){
                return new int[]{map.get(nums[i])+1,i+1};
            }
            map.put(target - nums[i],i);
        }
        return null;
    }
}

C++ solution

使用一个哈希表来解，第一遍扫描，保存到哈希表中，第二遍扫，看target-n在不在哈希表中，时间复杂度为O(n)。

class Solution {
public:
    vector<int> twoSum(vector<int> &numbers, int target) {
        map<int, int> mapping;
        vector<int> res;
        for (int i = 0; i < numbers.size(); ++i) {
            mapping[numbers[i]] = i;
        }
        for (int i = 0; i < numbers.size(); i++) {
            int searched = target - numbers[i];
            if (mapping.find(searched) != mapping.end() && i != mapping[searched]) {
                res.push_back(i + 1);
                res.push_back(mapping[searched] + 1);
                break;
            }
        }
        return res;
    }
};

class Solution {
public:
  /**
   * 
   * @param numbers int整型vector 
   * @param target int整型 
   * @return int整型vector
   */
  vector<int> twoSum(vector<int>& numbers, int target) {
    unordered_map<int, int> m;
    for (int i = 0; i < numbers.size(); ++i) {
      if (m.find(target - numbers[i]) != m.end())
        return {m[target - numbers[i]], i + 1};
      m[numbers[i]] = i + 1;
    }
    return {-1, -1};
  }
};

class Solution:
    def twoSum(self , numbers: List[int], target: int) -> List[int]:
        # write code here
        tm= {}
        res = []
        for i, v in enumerate(numbers):
            if v in tm:
                res.append(tm[v]+1)
                res.append(i+1)
            else:
                tm[target - v] = i
        return res

int* twoSum(int* numbers, int numbersLen, int target, int* returnSize ) {
    // write code here
    int *result = malloc(8);
    *returnSize = 2;
    for(int i = 0; i < numbersLen; i++)
    {
        // 过滤本身已经超过target的值，可以节省很多时间
        if(numbers[i]>target)
            continue;
        for(int j = i+1;j < numbersLen; j++)
            if(numbers[i]+numbers[j] == target)
            {
                *result = i+1;
                *(result+1) = j+1;
                return result;
            }
    }
    return NULL;
}

/**
  * 
  * @param numbers int整型一维数组 
  * @param target int整型 
  * @return int整型一维数组
  */
function twoSum( numbers ,  target ) {
    const map = new Map()
    for(let i = 0;i < numbers.length;i++){
        if(map.get(target - numbers[i]) !== undefined){
            return [map.get(target - numbers[i])+1,i+1]
        }
        map.set(numbers[i],i)
    }
}
module.exports = {
    twoSum : twoSum
};

Leetcode#1.Two Sum（两数之和）

package Array;
import java.util.Arrays;
import java.util.HashMap;
/**
 * 1.Two Sum（两数之和）
 * 给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。
 * 你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。
 */
public class Solution1 {
    public static void main(String[] args) {
        Solution1 solution1 = new Solution1();
        int[] nums = {2, 7, 11, 15};
        int target = 9;
        int[] result = solution1.twoSum(nums, target);
        System.out.println(Arrays.toString(result));
    }
    /**
     * 用 HashMap 存储数组元素和索引的映射，在访问到 nums[i] 时，判断 HashMap 中是否存在 target - nums[i]
     * 如果存在说明 target - nums[i] 所在的索引和 i 就是要找的两个数。
     * 该方法的时间复杂度为 O(N)，空间复杂度为 O(N)，使用空间来换取时间。
     *
     * [@param nums
     * @param target
     * @return](/profile/547241) */
    public int[] twoSum_2(int[] nums, int target) {
        HashMap map = new HashMap();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(target - nums[i])) {
                return new int[]{map.get(target - nums[i]) + 1, i + 1};
            } else {
                map.put(nums[i], i);
            }
        }
        return null;
    }
    /**
     * 暴力，时间复杂度为 O(N^2)
     *
     * [@param nums
     * @param target
     * @return](/profile/547241) */
    public int[] twoSum(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] + nums[j] == target) {
                    return new int[]{i + 1, j + 1};
                }
            }
        }
        return null;
    }
}

import java.util.*;
public class Solution {
    /**
     * 
     * @param numbers int整型一维数组 
     * @param target int整型 
     * @return int整型一维数组
     */
    public int[] twoSum (int[] numbers, int target) {
        int len = numbers.length;
        int[] result = new int[2];
        for(int i = 0; i < len; i++) {
            for(int j = i+1; j < len; j++) {
                if(numbers[i] + numbers[j] == target) {
                    result[0] = i + 1;
                    result[1] = j + 1;
                }
            }
        }
        return result;
    }
}

class Solution {
public:
    vector<int> twoSum(vector<int> &numbers, int target) {
        map<int, int> m;
        vector<int> res;
        for(int i=0; i<numbers.size(); i++){
            m[numbers[i]] = i;
        }
        for(int i=0; i<numbers.size(); i++){
            const int diff = target - numbers[i];
            if(m.find(diff) != m.end() && m[diff] > i){
                res.push_back(i+1);
                res.push_back(m[diff]+1);
                break;
            }
        }
        return res;
    }
};

使用一个map保存每一个不同的数字最后出现的坐标，然后从下标0处开始进行查找。
即使有重复的数字，由于map中保存的是最后一次出现的位置，那样即使由两个相同
的值构成的数对也可以被找到。m[diff] > i，这个条件使用的比较好。

# 用例全部通过版本：
class Solution:
    def twoSum(self , numbers: List[int], target: int) -> List[int]:
        # write code here
        for i in range(len(numbers) - 1):
            if numbers[i] <= target: # 用于降低时间复杂度
                for j in range(i+1, len(numbers)):
                    if numbers[i] + numbers[j] == target:
                        return [i+1, j+1]
        return []

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        unordered_map<int, int> hash;
        hash[numbers[0]]=1;
        for(int i=2;i<=numbers.size();++i){
            if(hash.count(target-numbers[i-1])){
                return {hash[target-numbers[i-1]], i};
            }
            else {
                hash[numbers[i-1]]=i;
            }
        }
        return {};
    }
};

 HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
        for(int i = 0; i < numbers.length; ++i){
            if(map.containsKey(target - numbers[i])){
                return new int[]{map.get(target - numbers[i]), i + 1};
            }else {
                map.put(numbers[i], i + 1);
            }
        }
        return null;