[LeetCode III – the sum of two Numbers input orderly array] | punch brush

Has been the habit of brush, recently saw the nuggets held a brush activities, especially to participate in! This is the third question in this participation.

This article is participating in the nuggets team online activity, clickCheck spring recruitment positions in big factories

I. Title Description:

Sum of two numbers II – Enter an ordered array

Given an array of integers in ascending order numbers, find two numbers that add up to the target number.

The function should return the subscript values of these two numbers as an array of integers of length 2. The subscript of numbers starts at 1, so the answer array should be 1 <= 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.

Example 1:

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

Example 2:

Numbers = [2,3,4] target = 6Copy the code

Example 3:

Numbers = [-1,0] target = -1Copy the code

Ii. Analysis of Ideas:

methods
describe
Time complexity
Spatial complexity
Double pointer method Opposite double pointer
O ( N ) O(N)
( 1 ) (1)
The first step Initialize thestartandendTwo hands
O ( N ) O(N)
( 1 ) (1)
The second step To calculatestartandendSum of two positional elementscurrentTarget
O ( N ) O(N)
( 1 ) (1)
The third step currentTarget 和targetIf the value is equal, returnstart+.end+1
O ( N ) O(N)
( 1 ) (1)
The fourth step currentTarget>target, then the pointer moves to the left,end--
O ( N ) O(N)
( 1 ) (1)
Step 5 currentTarget<target, then the pointer moves right,start++
O ( N ) O(N)
( 1 ) (1)

Iii. AC Code:

// @lc code=start
class Solution {
    public int[] twoSum(int[] numbers, int target) {
        // back conditions
        if (numbers == null || numbers.length == 0) {
            return new int[] { 0.0 };
        }

        int start = 0;
        int end = numbers.length - 1;
        while (start < end) {
            int currentTarget = numbers[start] + numbers[end];
            if (currentTarget < target) {
                start++;
            } else if (currentTarget > target) {
                end--;
            } else {
                // index begin is 1
                return new int[] { start + 1, end + 1}; }}return new int[] { 0.0}; }}// @lc code=end

Copy the code

Iv. Summary:

Given target and nums[I], this problem still belongs to the problem of finding nums[j], and this problem belongs to one kind of dual pointer.