Two Sum的變化題,輸入的陣列參數為已排序的整數。
題目
Given a 1-indexed array of integers numbers
that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target
number. Let these two numbers be numbers[index1]
and numbers[index2]
where 1 <= index1 < index2 <= numbers.length
.
Return the indices of the two numbers, index1
and index2
, added by one as an integer array [index1, index2] of length 2.
The tests are generated such that there is exactly one solution. You may not use the same element twice.
Your solution must use only constant extra space.
Example 1:
Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore, index1 = 1, index2 = 2. We return [1, 2].
Example 2:
Input: numbers = [2,3,4], target = 6
Output: [1,3]
Explanation: The sum of 2 and 4 is 6. Therefore index1 = 1, index2 = 3. We return [1, 3].
Example 3:
Input: numbers = [-1,0], target = -1
Output: [1,2]
Explanation: The sum of -1 and 0 is -1. Therefore index1 = 1, index2 = 2. We return [1, 2].
Constraints:
2 <= numbers.length <= 3 * 104
-1000 <= numbers[i] <= 1000
numbers
is sorted in non-decreasing order.-1000 <= target <= 1000
- The tests are generated such that there is exactly one solution.
先想到的解法
之前寫過Two sum的題目,所以應該不會再用一樣的方式解。想到用一個while廽圈兩個索引一個由陣列前往後、一個由後往前遍歷直到索引相交。前後元素相加若大於target則後索引往前移動;若前後元素相加小於target則前索引往前移動。時間複雜度應該是O(n)。
nums=[2,7,11,15], target=[9]
L1:=================================================================
v (i=nums.length - 1)
nums=[2,7,11,15]
^ (j=0)
L2:=================================================================
v (i=nums.length - 2)
nums=[2,7,11,15]
^ (j=0)
L3:=================================================================
v (i=nums.length - 3)
nums=[2,7,11,15]
^ (j=0)
Main.java
package com.abc.demo;
import java.util.Arrays;
public class Main {
public static void main(String[] arges) {
System.out.println(Arrays.toString(twoSum(new int[]{2, 7, 11, 15}, 9)));
System.out.println(Arrays.toString(twoSum(new int[]{2, 3, 4}, 6)));
System.out.println(Arrays.toString(twoSum(new int[]{-1, 0}, -1)));
}
public static int[] twoSum(int[] numbers, int target) {
int i = 0;
int j = numbers.length - 1;
while (i < j) {
int sum = numbers[i] + numbers[j];
if (sum == target) {
return new int[]{i + 1, j + 1};
}
if (sum > target) {
j--;
} else {
i++;
}
}
return new int[0];
}
}
更加解
上面在LeetCode只贏過14%左右的提交,但看了前面的提交解法都相同,所以應該沒其他更好的解法。
沒有留言:
張貼留言