1.TWO SUM

##

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

Code：

def twoSum(self, nums, target):

        # 相当于哈希表
        dic = {}
        rList = []
        valueList = []

        # 我们要求的是元素的索引，即Hash表的关键字，所以我们把数组元素作为dict的key
        # 而把数组元素的索引作为dict的value
        # 此时dic[2]=0,dic[7]=1,dic[11]=2,dic[15]=3
        for i in range(len(nums)):
            dic[nums[i]] = i

        for i in range(len(nums)):
            # 防止将同一对符合条件的值重复加入，防止结果出现[0,1],[1,0]
            # i=0循环后，进入i=1时，1已经存在rList中所以会跳过，节省时间
            if i not in rList:
                # 将符合条件的两个元素成为互补元素
                # 差值是字典的key且对应互补元素的下标不是当前元素的下标
                # i=0时为例:9-2=7->dic[7]存在 and dic[7]=1!=0,所以i=0符合条件
                if (target - nums[i]) in dic.keys() and dic[target - nums[i]] != i:
                    # 当前元素没有参与过之前的互补配对
                    # valueList初始为null
                    if nums[i] not in valueList:
                        # rList = {0,1}
                        rList.append(i)
                        rList.append(dic[target - nums[i]])
                # valueList = {2}
                valueList.append(nums[i])

        return rList

JAVA:

class Solution {
   public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> tracker = new HashMap<Integer, Integer>();
        int len = nums.length;
        for(int i = 0; i < len; i++){
            if(tracker.containsKey(nums[i])){
                int left = tracker.get(nums[i]);
                return new int[]{left, i};
            }else{
                tracker.put(target - nums[i], i);
            }
        }
        return new int[2];
    }
}