[LeetCode][167. Two Sum II - Input Array Is Sorted] 4 Approaches: Brute Force, HashMap, Binary Search, Two Pointers

发表于 更新于 分类于 Waline： 阅读次数： 本文字数： 2.8k 阅读时长 ≈ 3 分钟

By Long Luo

This article is the solution 4 Approaches: Brute Force, HashMap, Binary Search, Two Pointers of Problem 167. Two Sum II - Input Array Is Sorted.

Here shows 4 Approaches to slove this problem: Brute Force, HashMap, Binary Search, Two Pointers.

Brute Force

It’s easy to use Brute Force to find the answer, however, the time complexity is \(O(n^2)\), so the BF solution will Time Limit Exceeded!

1
2
3
4
5
6
7
8
9
10
11
12
public static int[] twoSum_bf(int[] numbers, int target) {
    int len = numbers.length;
    for (int i = 0; i < len; i++) {
        for (int j = i + 1; j < len; j++) {
            if (numbers[i] + numbers[j] == target) {
                return new int[]{i + 1, j + 1};
            }
        }
    }

    return new int[0];
}

Analysis

  • Time Complexity: \(O(n^2)\).
  • Space Complexity: \(O(1)\).

HashMap

We can use a extra \(\texttt{HashMap}\) to record the element we traversalled.

1
2
3
4
5
6
7
8
9
10
11
12
13
public static int[] twoSum_hash(int[] numbers, int target) {
    int len = numbers.length;
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < len; i++) {
        if (map.containsKey(target - numbers[i])) {
            return new int[]{map.get(target - numbers[i]), i + 1};
        }

        map.putIfAbsent(numbers[i], i + 1);
    }

    return new int[0];
}

Analysis

  • Time Complexity: \(O(n)\).
  • Space Complexity: \(O(n)\).

Binary Search

Since the array is already sorted, so we can use the binary search. In case of duplicated answer, we search only on the right of the left element.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int[] twoSum_bs(int[] numbers, int target) {
    for (int i = 0; i < numbers.length; ++i) {
        int low = i + 1;
        int high = numbers.length - 1;
        while (low <= high) {
            int mid = (high - low) / 2 + low;
            if (numbers[mid] == target - numbers[i]) {
                return new int[]{i + 1, mid + 1};
            } else if (numbers[mid] > target - numbers[i]) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
    }
    return new int[]{-1, -1};
}

Analysis

  • Time Complexity: \(O(nlogn)\).
  • Space Complexity: \(O(1)\).

Two Pointers

  1. Let the two pointers point to the position of the first element and the position of the last element;
  2. Each time the sum of the two elements pointed to by the two pointers is calculated and compared with the target value.
  3. A unique solution is found if the sum of the two elements equals the target value.
  4. If the sum of the two elements is less than the target, move the left pointer to the right one place; If the sum of the two elements is greater than the target, move the right pointer to the left by one.
  5. Repeat until you find the answer.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static int[] twoSum_tp(int[] numbers, int target) {
    int len = numbers.length;
    int left = 0;
    int right = len - 1;
    while (left < right) {
        if (numbers[left] + numbers[right] > target) {
            right--;
        } else if (numbers[left] + numbers[right] < target) {
            left++;
        } else {
            return new int[]{left + 1, right + 1};
        }
    }

    return new int[]{-1, -1};
}

Analysis

  • Time Complexity: \(O(n)\).
  • Space Complexity: \(O(1)\).

All suggestions are welcome. If you have any query or suggestion please comment below. Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗