-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy path_0167TwoSumiiInputArrayIsSorted.java
More file actions
91 lines (85 loc) · 3.01 KB
/
Copy path_0167TwoSumiiInputArrayIsSorted.java
File metadata and controls
91 lines (85 loc) · 3.01 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
package com.heatwave.leetcode.problems;
import java.util.Arrays;
/**
* 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.
* <p>
* Return the indices of the two numbers, index1 and index2, added by one as an integer array [index1, index2] of length 2.
* <p>
* The tests are generated such that there is exactly one solution. You may not use the same element twice.
* <p>
* Your solution must use only constant extra space.
* <p>
*
* <p>
* Example 1:
* <p>
* Input: numbers = [2,7,11,15],>
* Output: [1,2]
* Explanation: The sum of 2 and 7 is 9. Therefore, index1 = 1, index2 = 2. We return [1, 2].
* Example 2:
* <p>
* Input: numbers = [2,3,4],>
* Output: [1,3]
* Explanation: The sum of 2 and 4 is 6. Therefore index1 = 1, index2 = 3. We return [1, 3].
* Example 3:
* <p>
* Input: numbers = [-1,0],>
* Output: [1,2]
* Explanation: The sum of -1 and 0 is -1. Therefore index1 = 1, index2 = 2. We return [1, 2].
*
* <p>
* Constraints:
* <p>
* 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.
* <p>
* 来源：力扣（LeetCode）
* 链接：https://leetcode.cn/problems/two-sum-ii-input-array-is-sorted
* 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/
public class _0167TwoSumiiInputArrayIsSorted {
static class Solution {
public int[] twoSum(int[] numbers, int target) {
int left = 0, right;
while (true) {
right = left + 1;
while (right < numbers.length) {
int res = numbers[left] + numbers[right];
if (res == target) {
return new int[]{left + 1, right + 1};
}
if (res > target) {
break;
}
right++;
}
left++;
}
}
}
static class AnotherSolution {
public int[] twoSum(int[] numbers, int target) {
int n = numbers.length;
int left = 0, right = n - 1;
while (true) {
int sum = numbers[left] + numbers[right];
if (sum == target) {
return new int[]{left + 1, right + 1};
} else if (sum < target) {
left++;
} else {
right--;
}
}
}
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] nums = new int[]{2, 7, 11, 15};
int[] ints = solution.twoSum(nums, 9);
System.out.println(Arrays.toString(ints));
}
}