Leetcode 1. Two Sum
文章目录
这道题本身不难,我认为关键是要给出靠谱的证明。方法是先排序,然后首末各放一个指针进行移动。如果小了,左指针向右移,如果大了,右指针向左移。
证明应该就是要靠数学归纳法,证明每次正确答案应该在移动之后的两个指针之间。
public class Solution {
public int[] twoSum(int[] nums, int target) {
// 1. sort
List<Integer> inputs = new ArrayList<Integer>();
for (int num : nums) {
inputs.add(num);
}
Collections.sort(inputs);
// 2. iterate
int length = nums.length;
int p = 0;
int q = length - 1;
while (p < q) {
if (inputs.get(p) + inputs.get(q) < target) {
p++;
} else if (inputs.get(p) + inputs.get(q) > target) {
q--;
} else {
break;
}
}
for (int i = 0; i < length; i++) {
if (nums[i] == inputs.get(p)) {
p = i;
break;
}
}
for (int i = length - 1; i >= 0; i--) {
if (nums[i] == inputs.get(q)) {
q = i;
break;
}
}
int result[] = {p,q};
return result;
}
}
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论