【leetcode 167. Two Sum II - Input array is sorted】（两数之和）

【leetcode 167. Two Sum II - Input array is sorted】（两数之和）

题目链接 Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number. The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Note: Your returned answers (both index1 and index2) are not zero-based. You may assume that each input would have exactly one solution and you may not use the same element twice. Example: Input: numbers = [2,7,11,15], target = 9 Output: [1,2] Explanation: The sum of 2 and 7 is 9. Therefore index1 = 1, index2 = 2. 思路： 两数和为target，返回元素的位置。 大致和【leetcode 1. Two Sum】相同，不同的是所给的序列是递增的。 1. 用HashMap O(nlogn) Java： import java.util.HashMap; public class Solution { public int[] twoSum(int[] numbers, int target) { HashMap hashMap = new HashMap(); int[] res = new int[2]; for (int i = 0; i < numbers.length; i++) { if (hashMap.get(target - numbers[i]) == null) { hashMap.put(numbers[i], i + 1); } else { res[0] = hashMap.get(target - numbers[i]); res[1] = i + 1; break; } } return res; } public static void main(String[] args) { int[] numbers = { 2, 7, 11, 15 }; int target = 9; int[] res = new Solution().twoSum(numbers, target); System.out.println(res[0] + " " + res[1]); } } 2 优化。 因为本题中给定数组是递增的，只需要两个索引，依次遍历即可。 复杂度O(n) Java : import java.util.HashMap; public class Solution { public int[] twoSum(int[] numbers, int target) { int l = 0, r = numbers.length - 1; int[] res = new int[2]; while (l < r) { int sum = numbers[l] + numbers[r]; if (sum > target) r--; else if (sum < target) l++; else { res[0] = l + 1; res[1] = r + 1; break; } } return res; } public static void main(String[] args) { int[] numbers = { 2, 7, 11, 15 }; int target = 9; int[] res = new Solution().twoSum(numbers, target); System.out.println(res[0] + " " + res[1]); } }

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。