题目链接
题目描述
输入一个数组和一个数字 s,在数组中查找两个数,使得它们的和正好是 s。
如果有多对数字的和等于 s,输出任意一对即可。
你可以认为每组输入中都至少含有一组满足条件的输出。
数据范围:数组长度 [1,1002]。
输入:[1,2,3,4] , sum=7
输出:[3,4]
题目分析
数组排序 + 双指针
代码实现
class Solution {
public int[] findNumbersWithSum(int[] nums, int target) {
int[] res = new int[2];
Arrays.sort(nums);
int left = 0, right = nums.length - 1;
while(left < right){
int sum = nums[left] + nums[right];
if(sum == target){
res[0] = nums[left];
res[1] = nums[right];
return res;
}else if(sum > target){
right --;
}else{
left ++;
}
}
return res;
}
}
拓展
其实也可以通过哈希表实现
拓展题目
两数之和
给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那 两个 整数,并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
输入:nums = [2,7,11,15], target = 9
输出:[0,1]
解释:因为 nums[0] + nums[1] ==9 ,返回 [0, 1] 。
输入:nums = [3,2,4], target = 6
输出:[1,2]
输入:nums = [3,3], target = 6
输出:[0,1]
class Solution {
// 返回的是数组下标
public int[] twoSum(int[] nums, int target) {
int[] res = new int[2];
// key是nums中的值,value是下标
Map<Integer, Integer> hashMap = new HashMap<>();
for(int i = 0; i < nums.length; i ++){
int need = target - nums[i];
if(hashMap.containsKey(need)){
res[0] = i;
res[1] = hashMap.get(need);
return res;
}
hashMap.put(nums[i], i);
}
return res;
}
}