For 3 minutes a day, take the algorithmic counterattack route.

Handled in the collection

A daily collection of LeetCode preambles

Code warehouse

Making: github.com/meteor1993/…

Gitee: gitee.com/inwsy/LeetC…

Title: Sum of two numbers II – Enter an ordered array

Title source: leetcode-cn.com/problems/tw…

Given an ordered array that has been sorted in ascending order, find two numbers that add up to the target number.

The function should return the two subscripts index1 and index2, where index1 must be less than index2.

Description:

  • The subscripts returned (index1 and index2) do not start from zero.
  • You can assume that each input corresponds to a unique answer, and you can’t reuse the same elements.

Example:

Numbers = [2, 7, 11, 15] target = 9 So index1 = 1, index2 = 2.Copy the code

Programme 1: Violence law

This question I remember right words should be I do the deformation of the first question, read my article said not to do their own place to draw circles.

The simplest way to think about it is a violent iteration, which is O(n^2) in time and O(1) in space, and the code is incredibly simple, just two cycles of violence.

public int[] twoSum(int[] numbers, int target) {
    for (int i = 0; i < numbers.length; i++) {
        for (int j = i + 1; j < numbers.length; j++) {
            if (target - numbers[i] == numbers[j]) {
                return new int[] {i + 1, j + 1}; }}}return null;
}
Copy the code

Other than taking a little too long, it’s fine.

Scheme two: hash table

The brute force method above takes too long to find the second number, so we can find the second number in one loop by using the hash table.

/ / a hash table
public int[] twoSum_1(int[] numbers, int target) {
    Map<Integer, Integer> map = new HashMap<>(numbers.length);
    for (int i = 0; i < numbers.length; i++) {
        if (map.containsKey(target - numbers[i])) {
            return new int[] {map.get(target - numbers[i]) + 1, i + 1};
        }
        map.put(numbers[i], i);
    }
    return null;
}
Copy the code

It took a while, but only beat 36.12 percent of the respondents, suggesting there must be a better plan.

Plan three: dichotomy

I’m not going to explain this, but you know from the name, it’s a plan that takes half from the middle.

/ / dichotomy
public int[] twoSum(int[] numbers, int target) {
    for (int i = 0; i < numbers.length; i++) {
        int low = i + 1, 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 null;
}
Copy the code

It seems that dichotomy is not as fast as the hash table above.

Scheme 4: Dual Pointers

A double pointer is, as its name implies, two Pointers, one moving from front to back and one moving from back to front, based entirely on the fact that the current array is an ordered array.

/ / double pointer
public int[] twoSum_3(int[] numbers, int target) {
    int left  = 0, right = numbers.length - 1;
    while (left < right) {
        int sum = numbers[left] + numbers[right];
        if (target == sum) {
            return new int[] {left + 1, right + 1};
        } else if (sum < target){
            ++left;
        } else{ --right; }}return null;
}
Copy the code

This scheme is entirely based on ordered arrays. If it is unordered, it cannot be used. Its worst case is O(n), and the entire array loop, if not worst, is better than O(n).