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