1TwoSum.org

[#C] 1 Two Sum - LeetCode

思路： 遍历数组，每一次循环查找是否存在 target - nums[i] 。由于要返回的是索引，所以要用 Map 来记录数值和索引的对应关系。

Java

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer,Integer> map = new HashMap();
        for (int i = 0; i < nums.length; i++){
            int res = target - nums[i];
            if (map.containsKey(res)){
                return new int[] {i, map.get(res)};
            }
            map.put(nums[i],i);
        }
        throw new IllegalArgumentException("No two sum solution");
    }
}

CPP

#include<iostream>
#include<vector>
#include<cassert>
#include<unordered_map>

using namespace std;

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int taget) {
        unordered_map<int,int> record;

        for (int i = 0; i < nums.size(); i++) {
            int complement = target - nums[i];
            if (record.find(complement) != record.end()) {
                int res[2] = {i, record[complemente]};
                return vector<int>(res,res+2);
            }
            // 不能一次性放到map中，这是因为如果有两个数相同会把之前的覆盖，所以要一边查找，一边放入map 中
            record[nums[i]] = i;
        }

        throw invalid_argument("the input has no solution");
    }
};