- 浏览: 173778 次
- 性别:
- 来自: 济南
文章分类
最新评论
2sum, 3sum, 4sum和3sum closest是四道类似的题目,后面三个都是2sum的延伸。
1,2sum
给定一个数组numbers[]和一个目标数值target,从数组中找到两个元素,使它们的和等于目标元素。返回这两个值的索引indices,并且index1 大于index2。(假设只有一个结果)
例如:输入: numbers={2, 7, 11, 15}, target=9
输出: index1=1, index2=2 (不是zero-based)
我们用hash来实现这道题,key中存放数组里面元素的值number[i], value中存放对应的下标,hash(numbers[i], i)。我们从第一个元素开始遍历,检查表中是否存在一个key与target- numbers[i]相等,如果存在,那么结果就是这个key对应的value和当前的i的值,它们就是我们要找的下标;如果不存在就把<number[i], i>放入哈希表中,我们看到他的输出不是zero-based的,要将它们原始下标加1. 代码如下:
2,3sum
给定一个数组nums[],从中找出三个数使它们的和等于0,输出所有可能的结果。
例如:给定数组 nums[] = {-1 0 1 2 -1 -4};
输出: (-1, 0, 1), (-1, -1, 2) **结果集中的元素是有序的,并且结果集中不能重复
3sum是2sum的变形,我们用两个指针来处理这个问题,分别为left和right。因为结果是有序的,我们首先对数组进行排序。例如我们查找到第i个元素开查找,循环的开始right都指向最后一个元素,left指向i的下一个元素i + 1;然后比较nums[i] + nums[left] + nums[right] 是否为零,如果为零就输出结果,然后让left ++,right --,继续查找其他可能的结果;如果它们的和小于零,我们就让left ++; 如果它们的和大于零,就让right--;这个过程中我们要保证left始终小于right。代码如下:
3,4sum
给定一个数组nums[]和一个目标元素target,找出四个数,使他们的和等于target,输出所有可能的结果。
例如:给定数组nuts[] = {1 0 -1 0 -2 2} , target = 0.
输出:(-1, 0, 0, 1), (-2, -1, 1, 2), (-2, 0, 0, 2)
**结果集中的元素是有序的,并且结果集中不能重复
在3sum上的变形,首先也要对数组进行排序,然后我们只需要多加一个循环,用两个指针进行比较,不过只是用四个数的和与target比较而已。代码如下:
4,3sum Closest
给定一个数组nums[] 和一个目标元素target,从数组中找出三个元素,使它们的和最接近target,输出这三个元素的和。
例如:nums[] = {-1 2 1 -4}, and target = 1
输出:2 **因为 (-1 + 2 + 1 = 2)距离target最近
我们先按照3sum的思路,首先对数组进行,然后设定两个指针left和right,从第一个元素开始处理。理想情况下,如果找到三个数的和等于target,它们的距离为0,直接输出target。但是我们不能保证数组中一定存在三个数的和等于target,我们首先维护一个变量des,让它记录三个数的和与target的差值,每次比较des与当然的循环中的currentdes,如果currentdes小于全局的des,我们就用result记录当前三个数的和,直接从代码开来比较直观:
1,2sum
给定一个数组numbers[]和一个目标数值target,从数组中找到两个元素,使它们的和等于目标元素。返回这两个值的索引indices,并且index1 大于index2。(假设只有一个结果)
例如:输入: numbers={2, 7, 11, 15}, target=9
输出: index1=1, index2=2 (不是zero-based)
我们用hash来实现这道题,key中存放数组里面元素的值number[i], value中存放对应的下标,hash(numbers[i], i)。我们从第一个元素开始遍历,检查表中是否存在一个key与target- numbers[i]相等,如果存在,那么结果就是这个key对应的value和当前的i的值,它们就是我们要找的下标;如果不存在就把<number[i], i>放入哈希表中,我们看到他的输出不是zero-based的,要将它们原始下标加1. 代码如下:
public class Solution { public int[] twoSum(int[] nums, int target) { int[] result = new int[2]; HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>(); for (int i = 0; i < nums.length; i++) { int tem = target - nums[i]; if(hm.containsKey(tem)){ result[0] = hm.get(tem) + 1; result[1] = i + 1; } else { hm.put(nums[i], i); } } return result; } }
2,3sum
给定一个数组nums[],从中找出三个数使它们的和等于0,输出所有可能的结果。
例如:给定数组 nums[] = {-1 0 1 2 -1 -4};
输出: (-1, 0, 1), (-1, -1, 2) **结果集中的元素是有序的,并且结果集中不能重复
3sum是2sum的变形,我们用两个指针来处理这个问题,分别为left和right。因为结果是有序的,我们首先对数组进行排序。例如我们查找到第i个元素开查找,循环的开始right都指向最后一个元素,left指向i的下一个元素i + 1;然后比较nums[i] + nums[left] + nums[right] 是否为零,如果为零就输出结果,然后让left ++,right --,继续查找其他可能的结果;如果它们的和小于零,我们就让left ++; 如果它们的和大于零,就让right--;这个过程中我们要保证left始终小于right。代码如下:
public class Solution { public List<List<Integer>> threeSum(int[] nums) { List<List<Integer>> llist = new ArrayList<List<Integer>>(); List<Integer> list = new ArrayList<Integer>(); Arrays.sort(nums); if(nums == null || nums.length < 3) return llist; for(int i = 0; i < nums.length; i++) { //optimize, skip duplicate element if(i > 0 && nums[i] == nums[i - 1]) continue; int l = i + 1; int r = nums.length - 1; while( l < r) { int sum = nums[i] + nums[l] + nums[r]; if(sum > 0) { r --; } else if(sum < 0) { l ++; } else { list.add(nums[i]); list.add(nums[l]); list.add(nums[r]); llist.add(new ArrayList<Integer>(list)); list.clear(); while(l < r && nums[l] == nums[l + 1]) l ++; while(l < r && nums[r] == nums[r - 1]) r --; l ++; r --; } } } return llist; } }
3,4sum
给定一个数组nums[]和一个目标元素target,找出四个数,使他们的和等于target,输出所有可能的结果。
例如:给定数组nuts[] = {1 0 -1 0 -2 2} , target = 0.
输出:(-1, 0, 0, 1), (-2, -1, 1, 2), (-2, 0, 0, 2)
**结果集中的元素是有序的,并且结果集中不能重复
在3sum上的变形,首先也要对数组进行排序,然后我们只需要多加一个循环,用两个指针进行比较,不过只是用四个数的和与target比较而已。代码如下:
public class Solution { public List<List<Integer>> fourSum(int[] nums, int target) { List<List<Integer>> llist = new ArrayList<List<Integer>>(); List<Integer> list = new ArrayList<Integer>(); if(nums == null || nums.length < 4) return llist; Arrays.sort(nums); for(int i = 0; i < nums.length - 3; i++) { for(int j = i + 1; j < nums.length - 2; j++) { int l = j + 1; int r = nums.length - 1; while(l < r) { int sum = nums[i] + nums[j] + nums[l] + nums[r]; if(sum > target) { r --; } else if (sum < target) { l ++; } else { list.add(nums[i]); list.add(nums[j]); list.add(nums[l]); list.add(nums[r]); if(!llist.contains(list)) llist.add(new ArrayList<Integer>(list)); list.clear(); while(l < r && nums[l] == nums[l+1]) l ++; while(l < r && nums[r] == nums[r-1]) r --; l ++; r --; } } } } return llist; } }
4,3sum Closest
给定一个数组nums[] 和一个目标元素target,从数组中找出三个元素,使它们的和最接近target,输出这三个元素的和。
例如:nums[] = {-1 2 1 -4}, and target = 1
输出:2 **因为 (-1 + 2 + 1 = 2)距离target最近
我们先按照3sum的思路,首先对数组进行,然后设定两个指针left和right,从第一个元素开始处理。理想情况下,如果找到三个数的和等于target,它们的距离为0,直接输出target。但是我们不能保证数组中一定存在三个数的和等于target,我们首先维护一个变量des,让它记录三个数的和与target的差值,每次比较des与当然的循环中的currentdes,如果currentdes小于全局的des,我们就用result记录当前三个数的和,直接从代码开来比较直观:
public class Solution { public int threeSumClosest(int[] nums, int target) { if(nums == null || nums.length < 3) return -1; int des = Integer.MAX_VALUE; int result = 0; Arrays.sort(nums); for(int i = 0; i < nums.length; i++) { int l = i + 1; int r = nums.length - 1; while(l < r) { int sum = nums[i] + nums[l] + nums[r]; if(sum == target) { return target; } else if(sum < target) { if(target - sum < des) { des = target - sum; result = sum; } l ++; } else { if(sum - target < des) { des = sum - target; result = sum; } r --; } } } return result; } }
发表评论
-
498. Diagonal Traverse
2019-11-15 13:52 227Given a matrix of M x N eleme ... -
496 Next Greater Element I
2019-11-14 13:50 228You are given two arrays (witho ... -
Word Break II
2016-03-09 03:15 343Given a string s and a dictiona ... -
Insert Interval
2016-03-08 02:11 335Given a set of non-overlapping ... -
Merge Intervals
2016-03-07 05:25 451Given a collection of intervals ... -
Merge k Sorted Lists
2016-03-07 04:03 513Merge k sorted linked lists and ... -
Multiply Strings
2016-03-06 07:27 431Given two numbers represented a ... -
N-Queens II
2016-03-06 03:06 622Follow up for N-Queens problem. ... -
N-Queens
2016-03-06 02:47 428The n-queens puzzle is the prob ... -
First Missing Positive
2016-03-05 03:09 388Given an unsorted integer array ... -
Spiral Matrix
2016-03-04 03:39 519Given a matrix of m x n element ... -
Trapping Rain Water
2016-03-04 02:54 534Given n non-negative integers r ... -
Repeated DNA Sequences
2016-03-03 03:10 371All DNA is composed of a series ... -
Increasing Triplet Subsequence
2016-03-02 02:48 862Given an unsorted array return ... -
Maximum Product of Word Lengths
2016-03-02 01:56 883Given a string array words, fin ... -
LRU Cache
2016-02-29 10:37 556Design and implement a data str ... -
Super Ugly Number
2016-02-29 07:07 601Write a program to find the nth ... -
Longest Increasing Path in a Matrix
2016-02-29 05:56 765Given an integer matrix, find t ... -
Coin Change
2016-02-29 04:39 736You are given coins of differen ... -
Minimum Height Trees
2016-02-29 04:11 630For a undirected graph with tre ...
相关推荐
js代码-16. 3Sum Closest
leetcode 答案LeetCode_1_TwoSum LeetCode 问题:给定一个整数数组,找出两个数字,使它们相加为特定的目标数字。 函数 twoSum 应该返回两个数字的索引,使它们相加为目标,其中 ...和 index2)不是从零开始的。
18 3Sum Closest 57 19 String to Integer (atoi) 59 20 Merge Sorted Array 61 ... ... 231 Counting Bits 561 232 Maximum Product of Word Lengths 563 233 Gray Code 565 234 Permutations 567 235 Permutations...
16. 3Sum Closest 17. Letter Combinations of a Phone Number 18. 4Sum 19. Remove Nth Node From End of List 20. Valid Parentheses 21. Merge Two Sorted Lists 22. Generate Parentheses 23. Merge k Sorted ...
lru cache ...Hash法转换2sum 9 3Sum Closest Sort +夹逼法 10 4Sum Sort +夹逼法 11 Remove Element 12 Next Permutation 公式 13 Permutation Sequence 公式 14 Valid Sudoku 15 Trapping Rain W
[3Sum Smaller.java]( Smaller.java) Java 6 [4 Sum.java]( Sum.java) Java 7 Java 8 [添加和搜索 Word.java](和搜索 Word.java) Java 9 [添加Binary.java](Binary.java) Java 10 [加两个数II.java]( 两个数II....
java lru leetcode Java算法问题 托管来自 LintCode、LeetCode 等算法问题的 Java 解决方案。 一旦出现新问题或新测试用例,我将尝试...[3Sum Smaller.java]( Smaller.java) Java 6 [4 Sum.java]( Sum.java) 中等的 J
[3 Sum Closest.java]( Sum Closest.java) Java 2个 [3 Sum.java]( Sum.java) Java 3 [4 Sum.java]( Sum.java) Java 4 Java 5 Java 6 [Balanced Binary Tree.java]( Binary Tree.java) Java 7 ...
leetcode 2 sum c leetcode 力扣(Leetcode)编程题,JavaScript版本。 编号 中文题目 英文题目 题目描述 JavaScript 难度 1 Two Sum 简单 2 Add Two Numbers ...3 ...3Sum ...3Sum Closest ...4Sum 中等 19 Remo
LeetCode刷题总结 1.Two Sum 2.Add Two Numbers 3.Longest Substring Without Repeating Characters 4.Median of Two Sorted Arrays 5.Longest Palindromic Substring (Manacher算法待完成) 6.ZigZag Conversion 7....
3Sum Closest 4Sum Remove Element Move Zeroes Next Permutation Permutation Sequence Valid Sudoku Trapping Rain Water Rotate Image Plus One Climbing Stairs Set Matrix Zeroes Gas Station Candy Majority ...
leetcode 530 ** LeetCode 题目更新 ** 用来记录业余时间所做的算法题目,保持对于数据结构的熟悉。...4Sum 020 Valid Parentheses 022 Generate Parentheses 028 Implement strStr() 031 Next Permutat
det[11][3] * (dp[3][0] - dp[3][2]); det[15][3] = det[7][0] * (dp[0][0] - dp[0][3]) + det[7][1] * (dp[1][0] - dp[1][3]) + det[7][2] * (dp[2][0] - dp[2][3]); } } //-------------------------------...
leetcode题库 LeetCode 题解合集 本仓库展示了LeetCode题库中部分题目的解法(持续更新),所有代码均采用C++编写...3Sum.cpp 最接近的三数之和 3Sum Closest .cpp 20 有效的括号 Valid Parentheses.cpp 22 括号生成 G
给定一个已排序的数组和一个数字x,在数组中找到总和最接近x的对 private static void printClosest(int[] arr, int n, int x) { int left = -1, right = -1; int diff = Integer.MAX_VALUE; for(int i=0, j=...
gas station ...p0016_3sum_closest; // pub mod p0018_4sum; pub mod p0003_longest_substring_without_repeating_characters; pub mod p0005_longest_palindromic_substring; pub mod p0007_reverse_int
2.Add Two Numbers 3.Longest Substring Without Repeating Characters 4.Median of Two Sorted Arrays 7.Reverse Integer 8.String to Integer (atoi) 9.Palindrome Number 11.Container With Most Water 14....
4 Median of Two Sorted Arrays 5 Longest Palindromic Substring 8 String to Integer 11 Container with Most Water 14 Longest Common Prefix 15 Three Sum 16 Three Sum Closest 20 Valid Parentheses 26 Remove...
leetcode中文版 LeetCode # Title Chinese Tag Solution 1 Two Sum 两数之和 array,hash 2 ...3 ...4 ...3Sum Closest 最接近的三数之和 two pointers,array 21 Merge Two Sorted Lists 合并两个有序链表 lin