This is the 13th day of my participation in the November Gwen Challenge. Check out the event details: The last Gwen Challenge 2021

Topic describes

Given an array of integers in non-decreasing order numbers, find two numbers that add up to the target number. The function should have length2Returns the subscript values of both numbers in the form of an array of integers. Numbers subscript from1Start counting, so the answer array should satisfy1 <= answer[0] < answer[1) < = Numbers. Length. You can assume that each input corresponds to a unique answer, and you can't reuse the same elements. The sample1: input: numbers = [2.7.11.15], target = 9Output:1.2] :2 与 7The sum is equal to the number of targets9. So the index1 =1, index2 = 2. The sample2: input: numbers = [2.3.4], target = 6Output:1.3] example3: Enter: numbers = [-1.0], target = -1Output:1.2] :2 <= numbers.length <= 3 * 104
-1000 <= numbers[i] <= 1000Numbers are in non-decreasing order -1000 <= target <= 1000Only one valid answer exists source: LeetCode//leetcode-cn.com/problems/two-sum-ii-input-array-is-sortedCopyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.Copy the code

Ideas & CODE

1. The hash

It seems that this kind of finding element of the problem can be hashed, but generally not optimal solution, comparison needs to open up extra space

Get (target- current element) is used to retrieve the current element index as long as map.get(target- current element) is not null. And, of course, they say I is less than j, so we have to evaluate the size of the element and return it

public int[] twoSum1(int[] numbers, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < numbers.length; i++) {
        map.put(numbers[i], i);
    }
    for (int i = 0; i < numbers.length; i++) {
        Integer index = map.get(target - numbers[i]);
        if(index ! =null) {
            if (i > index) {
                return new int[]{index+1, i+1};
            } else {
                return new int[]{i+1, index+1}; }}}return new int[] {-1, -1};
}
Copy the code

Time complexity O(n), space complexity O(n)

Binary search

And since they’re conditional, they’re increasing the array. So we iterate over an element, use target- this element to get another element, and then bisect after that element to find another element.

public int[] twoSum2(int[] numbers, int target) {
    for (int i = 0; i < numbers.length; i++) {
        int left = i + 1;
        int right = numbers.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (numbers[i] + numbers[mid] == target) {
                return new int[]{i + 1, mid + 1}; 
            } else if (numbers[i] + numbers[mid] < target) {
                left = mid + 1;
            } else if (numbers[i] + numbers[mid] > target) {
                right = mid - 1; }}}return new int[] {-1, -1};
}
Copy the code

Traversal takes n time, binary takes logn, so time is order logn.

3. Double pointer

When writing this topic, I looked at the tag. Although I saw the double pointer, I still couldn’t think of the solution after thinking for a long time.

Each time the loop computes the sum of the first pointer elements, and moves the left pointer to the right if it is less than target. Greater than target moves the right pointer to the left. The condition of the while is left < right. Returns the index position if the sum of the leading and trailing Pointers equals target

The problem with this solution is, will I miss elements if I move the pointer this way?

Read the solution found a wonderful idea!

Will not repeat the record, you can see the link below; In short, all of the combinations in this problem can fit into a rectangle, and this rectangle has n^2 little rectangles, and each little rectangle is a combination of elements. Violent loops exclude one small rectangle at a time, while double Pointers exclude one row (column) of rectangles at a time!

Use double Pointers to reduce the search space

public int[] twoSum3(int[] numbers, int target) {
    int left = 0;
    int right = numbers.length - 1;
    while (left < right) {
        if (numbers[left] + numbers[right] == target) {
            return new int[]{left + 1, right + 1};
        } else if (numbers[left] + numbers[right] > target) {
            right--;
        } else if(numbers[left] + numbers[right] < target) { left++; }}return new int[] {-1, -1};
}
Copy the code