首页 > 程序开发 > 软件开发 > 其他 >

Array167Two Sum II - Input array is sorted

2016-11-29

One failed case: [0,0,3,4] target: 0 Logic Loophole I initially wrote this line at the beginning of the loop if (numbers[j] >= target) j--; Then I find I didn’t consider the 0 case so changed into > rather than >= Code Optimization

思路1: Use two pointers

One failed case: [0,0,3,4] target: 0 Logic Loophole I initially wrote this line at the beginning of the loop if (numbers[j] >= target) j--; Then I find I didn’t consider the 0 case. so changed into > rather than >= Code Optimization My first-time solution twoSumByTwoPointers1() is not concise. see the twoSumByTwoPointers2() makes some thinking
Decrements of j are the same condition before and after locatingnumbers[j] ~~ target. If not consider time complexity, it can be merged The i and j won&rsquo;t miss any possibilities when i < j because i++ and j&ndash; are only solutions in respect of two potential conditions sum < targetand sum > target

思路2: BinarySearch + two pointers

* 用binarySearch找到end的初始位置, 然后用two pointers
* For the binary search, the start have to change, to better locate the mid. 

思路3: 纯BinarySearch

这个一开始没想出来的原因是, 我忘记了其实answer[1] = target - answer[0] 一旦想到这个, 就好做了. twoSumByBinarySearch1() 是别人写的, 非常简洁. 在Arrays的Java预设方法里面, 注意toIndex是exclusive的
fromIndex - the index of the first element (inclusive) to be searched
toIndex - the index of the last element (exclusive) to be searched
自己重写了BinarySearch with toIndex exclusive, 遇到了不少问题
[0, 0, 3, 4] 0
如果fromIndex == toIndex == 1 in this case, should return mid == 1 rather than break the loop and return -1; [5,25,75] 100 在第一轮运行BinarySearch() target = 95的时候, fromIndex == toIndex == 3 that out of Bounds 我不会做了. 看了别人的代码才发现, 首先应该在开始的时候赋值 int start = fromIndex, end = toIndex - 1 , 其次是因为很可能会带入numbers[end] 所以最好end = toIndex -1这样既不用担心start == end又不用担心溢出.
相关文章
最新文章
热点推荐