leetocode刷题（1）—— 1. 两数之和
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1]
解法1:
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int complement = target - nums[i];
if (map.containsKey(complement)) {
return new int[] { map.get(complement), i };
}
map.put(nums[i], i);
}
throw new IllegalArgumentException("No two sum solution");
}
}错误方法:双指针技巧 网上有说使用双指针解决，描述如下：
如果假设输入一个数组 nums 和一个目标和 target，请你返回 nums 中能够凑出 target 的两个元素的值，比如输入 nums = [1,3,5,6], target = 9，那么算法返回两个元素 [3,6]。可以假设只有且仅有一对儿元素可以凑出 target。 我们可以先对 nums 排序，然后利用前文 双指针技巧 写过的左右双指针技巧，从两端相向而行就行了
解法：
public class Solution1 {
public int[] twoSum(int[] nums, int target) {
Arrays.sort(nums);
int begin = 0;
int end = nums.length-1;
while(begin < end){
int beginVal = nums[begin];
int endVal = nums[end];
if(beginVal+endVal<target){
begin++;
}else if(beginVal+endVal>target){
end--;
}else if(beginVal+endVal == target){
return new int[]{begin,end};
}
}
return new int[]{-1,-1};
}
}**注意:**这里的问题在于，数组已经进行排序之后，如果原来是乱序的，排序后下标就不是原来的下标了，所以返回的下标是有问题的，这个解法不能在此使用
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2020-04-14，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
腾讯云开发者
