首页 > 代码库 > 2 Sum ,3 Sum, 3 Sum close
2 Sum ,3 Sum, 3 Sum close
1. Two Sum
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution.
Example:
Given nums = [2, 7, 11, 15], target = 9, Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1].
public class Solution { public int[] twoSum(int[] nums, int target) { int[] res = new int[2]; if(nums == null || nums.length == 0) return res; HashMap<Integer, Integer> map = new HashMap<>(); for(int i = 0; i < nums.length ; i++){ if(map.containsKey(target-nums[i])){ res[0] = map.get(target-nums[i]); res[1] = i; } map.put(nums[i], i); } return res; } }
3 Sum
Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Note: The solution set must not contain duplicate triplets.
For example, given array S = [-1, 0, 1, 2, -1, -4], A solution set is: [ [-1, 0, 1], [-1, -1, 2] ]
public class Solution { public List<List<Integer>> threeSum(int[] nums) { List<List<Integer>> res = new ArrayList<>(); Arrays.sort(nums); for(int i = 0 ; i < nums.length - 2; i++){ List<Integer> list = new ArrayList<>(); int left = i + 1; int right = nums.length -1; int sum = 0 - nums[i]; while(left < right){ if(nums[left] + nums[right] == sum){ list.add(nums[i]); list.add(nums[left]); list.add(nums[right]); if(!res.contains(list)) res.add(new ArrayList<>(list)); list.clear(); while(left < right && nums[left] == nums[left+1]) left++; while(left < right && nums[right] == nums[right-1]) right--; left++; right--; } else if(nums[left] + nums[right] < sum){ left ++; } else right--; } } return res; } }
16. 3Sum Closest
Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.
For example, given array S = {-1 2 1 -4}, and target = 1. The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
public class Solution { public int threeSumClosest(int[] nums, int target) { Arrays.sort(nums); int min = Integer.MAX_VALUE; for(int i = 0 ; i < nums.length -2; i++){ int left = i + 1; int right = nums.length - 1; int value = http://www.mamicode.com/target - nums[i]; while(left < right){ if(nums[left] + nums[right] == value) return target; if(min == Integer.MAX_VALUE || Math.abs(nums[i] + nums[left] + nums[right] - target) < Math.abs(min - target)) min = nums[i] + nums[left] + nums[right]; if(nums[left] + nums[right] > value) right --; else left++ ; } } return min; } }
2 Sum ,3 Sum, 3 Sum close
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。