Public account: Love to write bugs (ID: ICodebugs)

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

Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2.

Note:

  • Your returned answers (both index1 and index2) are not zero-based.
  • You may assume that each input would have exactly one solution and you may not use the same element twice.

Answer:

If the sum of the left and right Pointers is less than target, the left pointer moves to the right one bit. If the sum of the right and left Pointers is greater than target, the right pointer moves to the left one bit until the sum of the two Pointers equals Target.

Code (Java) :

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int[] res = new int[2];
        int i = 0, j = numbers.length - 1,temp;// I is the left pointer, j is the right pointer
        while (i < j) {
            temp=numbers[i] + numbers[j];// Count the sum of the two numbers
            if (temp == target) {// if the number is equal to the target, the index is recorded
                res[0] = i + 1;
                res[1] = j + 1;
                return res;
            } else if (temp < target) {// If the number is smaller than the target number, the left pointer moves to the right one bit
                i++;
            } else {// If the target number is greater than that, the right pointer moves one bit to the leftj--; }}return null; }}Copy the code

Code (python3) :

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        i=0
        j=len(numbers)- 1
        while i<j:
            if numbers[i]+numbers[j]==target:
                return i+1,j+1
            elif numbers[i]+numbers[j]>target:
                j-=1
            else:i+=1
Copy the code

Conclusion:

The question itself is pretty simple, with a few little details:

  • if (temp == target)Determining whether the number is the same as the target number reduces running time (because Leetcode runs with a lot of different data, rather than a very long one). Think about the difference here.)
  • temp=numbers[i] + numbers[j]Add the sum of the two numbers first. If you add the sum of the two numbers each time (== >), it will take more time.

Extension:

Find py3 behind an interesting solution, efficiency is not high, expand the train of thought can be:

class Solution(object):
    def twoSum(self, numbers, target):
        s = {}
        r = []
        for i in range(len(numbers)):
            if numbers[i] in s.keys():Check whether the number is present in the key of the s key pair. Because the keys of a key-value pair record the difference
                r.append(s[numbers[i]]+1)
                r.append(i+1)
                return r
            s[target-numbers[i]] = iThe difference between the target number and each number is recorded as the key of the S key-value pair, whose index is recorded as the value
        return None
Copy the code

Use py3 dictionary features to solve problems, very interesting.