Two Sum

Description

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

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

You can return the answer in any order.

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]

Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]

Constraints:

• 2 <= nums.length <= 104
• -109 <= nums[i] <= 109
• -109 <= target <= 109
• Only one valid answer exists.

Thoughts

1. Binary？
2. Search after sort？

Info

First review question: Two integers return array subscripts. The given array is not sorted. Is the returned array sorted?

Looking back, I discovered the overlooked factors: Do the arrays have the same elements?

Solution

1. Dual-Pointer

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] result = new int[2];
        int i,j;
	      //一个向前 一个向后，避免重复查找
        for(i = 0; i < nums.length;i++){
            for(j = nums.length-1; j>i; j--){
                if(nums[i]+nums[j] == target){
                    result[0] = i;
                    result[1] = j;
                    return result;
                }
            }
        }
        return null;
    }
}

Time complexity O(N²)

Space complexity O(1)

2. Hash

Indeed, I first thought of this when Boss Zheng came up with the question, but I was afraid that putting it into the map collection would consume a certain amount of time. Alas...

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map map = new HashMap<Integer,Integer>();
        int j ;
        for(int i =0; i<nums.length; i++){
            j = (int) map.getOrDefault(nums[i],-1);
            if(j != -1){
                return new int[]{j,i};
            }
            map.put(target - nums[i] , i);
        }
        return null;
    }
}

Time complexity: O(N)

Space complexity O(N)

Here, since the get method of the hash table has an overhead of O(1), we consider the hash table method to search directly. The subtlety lies in the flexible use of its index key.