LeetCode 167. Two Sum II — Input Array Is Sorted
Problem
Approach: Two Pointers
- Set the low pointer `lo` to start, and high pointer `ji` to the last index.
- While low pointer is smaller than high:
- Increment `lo`, if the sum of `nums[lo]` and `nums[hi]` is less than target,
or the value is the same as for `lo - 1`.
- Decrement `hi`, if the sum is greater than target,
Or the value is the same as for `hi + 1`.
- Otherwise, we found a pair:
- Add it to the result `res`.
- Decrement `hi` and increment `lo`.
- Return the result `res`.
Implementation
class Solution {
fun twoSum(numbers: IntArray, target: Int): IntArray {
val result = IntArray(2)
var j = 0
var k = numbers.size - 1
while (j < k) {
val sum = numbers[j] + numbers[k]
if (sum == target) {
result[0] = j + 1
result[1] = k + 1
break
} else if (sum < target) {
j++
} else {
k--
}
}
return result
}
}Complexity Analysis
- Time Complexity: O(n)
- Space Complexity: O(1)
