Two Sum

, , , , , ,

Question

You are given a list of numbers, and a target number k. Return whether or not there are two numbers in the list that add up to k.

Example

1
2
Given [4, 7, 1 , -3, 2] and k = 5,
return true since 4 + 1 = 5.

Solution

(1) The intuition solution for this problem would be use two for loop to process every pair and to see the sum of these two whether equals target.

(2) We can sort elements first and use two pointers to find if target exists.

(3) Using HashMap to record the index of number and see if target - currentNum exists in our HashMap.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

// time:O(n^2) space:O(1)
public boolean twoSum(int[] nums, int target) {
        if (nums == null || nums.length == 0) return false;
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] + nums[j] == target) return true;
            }
        }
        return false;
    }

// time:O(nlogn) space:O(1) 
public boolean twoSum(int[] nums, int target) {
        if (nums == null || nums.length == 0) return false;
        Arrays.sort(nums);
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int sum = nums[left] + nums[right];
            if (sum == target) {
                return true;
            } else if (sum > target) {
                right--;
            } else {
                left++;
            }
        }
        return false;
    }

// time:O(n) space:O(n)
public boolean twoSum3(int[] nums, int target) {
        if (nums == null || nums.length == 0) return false;
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (map.get(target - nums[i]) != null) return true;
            map.put(nums[i], i);
        }
        return false;
    }