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].

思路1： Brute force

暴力双循环，O(n^2)，不实现了吧

思路2：Two Pointers

先sort然后再双Pointer，O(nlogn)

public class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] nums_sort = new int[nums.length];
        System.arraycopy(nums,0,nums_sort,0,nums.length);

        Arrays.sort(nums_sort);

        int left = 0;
        int right = nums_sort.length-1;

        while(left<right){
            int sum2 = nums_sort[left]+nums_sort[right];
            if (sum2==target){
               break;
            }else if(sum2<target){
               left++;
            }else{
               right--;
            }
        }

        int[] result = new int[2];
        int index = 0;
        for (int i=0;i<nums.length;i++){
            if (nums[i]==nums_sort[left]||nums[i]==nums_sort[right]){
                result[index] = i;
                index++;
            }
        }

        return result;
    }
}

思路3：HashMap

巧妙使用HashMap，O(n)就可以了

    public int[] twoSum(int[] nums, int target) {
        int[] result = new int[2];
        HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();

        for (int i=0;i<nums.length;i++){
            if (map.containsKey(target-nums[i])){
                result[0] = map.get(target-nums[i]);
                result[1] = i;
                return result;
            }else{
                map.put(nums[i],i);
            }
        }
        return result;
    }
}

C++ code

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int> map;
        vector<int> res;
        for (int i=0; i<nums.size(); i++){
            int numberToFind = target - nums[i];

            if (map.find(numberToFind)!=map.end()){
                res.push_back(map[numberToFind]);
                res.push_back(i);
                return res;
            }else{
                map[nums[i]] = i;
            }
        }
        return res;
    }
};