00001 两数之和
题目描述
给定一个整数数组和一个目标值, 找出数组中和为目标值的两个数.
你可以假设每个输入只对应一种答案, 且同样的元素不能被重复利用.
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9, 所以返回 [0, 1]
力扣地址
- https://leetcode.com/problems/two-sum
- https://leetcode-cn.com/problems/two-sum
解题报告
暴力法
本题解由微信公众号小猿刷题提供, 错误之处, 欢迎指正.
暴力法很简单, 遍历每个元素 x, 并查找是否存在一个值与 target−x 相等的目标元素.
- /**
- * 微信公众号 "小猿刷题"
- */
- class Solution {
- public int[] twoSum(int[] nums, int target) {
- for (int i = 0; i <nums.length; i++) {
- for (int j = i + 1; j < nums.length; j++) {
- if (nums[j] == target - nums[i]) {
- return new int[] { i, j };
- }
- }
- }
- throw new IllegalArgumentException("No two sum solution");
- }
- }
哈希表
本题解由微信公众号小猿刷题提供, 错误之处, 欢迎指正.
为了优化运行时间复杂度, 引入哈希表来检查数组中是否存在目标元素. 如果存在, 则找出它的索引.
- /**
- * 微信公众号 "小猿刷题"
- */
- class Solution {
- public int[] twoSum(int[] nums, int target) {
- // 数字原始和其对应的下标映射
- Map<Integer, Integer> map = new HashMap<>();
- // Hash 表中检测是否存在匹配
- for(int i=0; i<nums.length; i++){
- int num = target - nums[i];
- if(map.containsKey(num)){
- return new int[]{map.get(num), i};
- } else {
- map.put(nums[i], i);
- }
- }
- throw new IllegalArgumentException("No two sum solution");
- }
- }
小猿刷题
00167 两数之和 II - 输入有序数组
题目描述
给定一个已按照 升序排列 的有序数组, 找到两个数使得它们相加之和等于目标数.
函数应该返回这两个下标值 index1 和 index2, 其中 index1 必须小于 index2.
说明:
返回的下标值 ( index1 和 index2 ) 不是从零开始的.
你可以假设每个输入只对应唯一的答案, 而且你不可以重复使用相同的元素.
示例:
输入: numbers = [2, 7, 11, 15], target = 9
输出: [1,2]
解释: 2 与 7 之和等于目标数 9 . 因此 index1 = 1, index2 = 2 .
力扣地址
- https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/
- https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted/
解题报告
哈希表
本题解由微信公众号小猿刷题提供, 错误之处, 欢迎指正.
遍历数组, 数组遍历的当前值为 nums[i], 那么 y 应该是 target - nums[i]; 所以只要在遍历的时候确定 target - nums[i] 在数组里有, 返回对应下标.
- /**
- * 微信公众号 "小猿刷题"
- */
- class Solution {
- public int[] twoSum(int[] nums, int target) {
- Map<Integer, Integer> map = new HashMap();
- for(int i = 0; i < nums.length; i ++){
- int cur = nums[i];
- int num = target - cur;
- if(map.containsKey(num)){
- return new int[] {map.get(num) + 1, i + 1};
- } else {
- map.put(cur, i);
- }
- }
- throw new IllegalArgumentException("No two sum solution");
- }
- }
双指针
本题解由微信公众号小猿刷题提供, 错误之处, 欢迎指正.
我们使用两个指针, 初始分别位于第一个元素和最后一个元素位置, 比较这两个元素之和与目标值的大小.
如果和等于目标值, 我们发现了这个唯一解. 如果比目标值小, 我们将较小元素指针增加一. 如果比目标值大, 我们将较大指针减小一. 移动指针后重复上述比较知道找到答案.
- /**
- * 微信公众号 "小猿刷题"
- */
- class Solution {
- public int[] twoSum(int[] nums, int target) {
- int low = 0;
- int high = nums.length - 1;
- while (low < high) {
- if (nums[low] + nums[high] == target) {
- return new int[] {low + 1, high + 1};
- }
- if (nums[low] + nums[high] < target) {
- low ++;
- } else {
- high --;
- }
- }
- throw new IllegalArgumentException("No two sum solution");
- }
- }
小猿刷题
来源: http://www.jianshu.com/p/d52b6d01e77c