Thursday, January 5, 2017

Leetcode/亚麻--167. Two Sum II - Input array is sorted(two pointer)

167. Two Sum II - Input array is sorted(two pointer)

https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/

思路: Two pointers. i start from 0, j start from len-1, add two as sum and compared to sum
          If smaller, i++, larger j--, else found
Complexity O(N)


3sum: i -start j-end, k-i+1
i need to skip duplicates
if get 0 j and k skip duplicates, j-- &k++, seek for next answer where i fixed

public class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int[] res =new int[2];
        int len =  numbers.length;
        int i=0,j=len-1;
        while(i<len&&j>0){
            int sum = numbers[i]+numbers[j];
            if(sum==target)break;
            if(sum<target)i++;
            else j--;
        }
        res[0]=i+1;
        res[1]=j+1;
        return res;
    }
}

No comments:

Post a Comment