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, and you may not use the same element twice.
Example:
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
- class Solution {
- public int[] twoSum(int[] nums, int target) {
- Map<Integer, Integer> map = new HashMap();
- for(int i = 0; i<nums.length; i++){
- map.put(nums[i], i);
- }
- for (int i = 0; i < nums.length; i++) {
- int complement = target - nums[i];
- if (map.containsKey(complement) && map.get(complement) != i) {
- return new int[] { i, map.get(complement) };
- }
- }
- return null;
- }
- }
- class Solution {
- public int[] twoSum(int[] nums, int target) {
- // corner cases
- if (nums == null || nums.length <= 1) {
- return null;
- }
- int[] nums2 = Arrays.copyOf(nums, nums.length);
- Arrays.sort(nums);
- int left = 0;
- int right = nums.length - 1;
- int a = 0;
- int b = 0;
- while (left < right) {
- long sum = (long) nums[left] + (long) nums[right];
- if (sum == target) {
- a = nums[left];
- b = nums[right];
- break;
- } else if (sum < target) {
- left += 1;
- } else {
- right -= 1;
- }
- }
- // find index 1
- for (int i = 0; i < nums2.length; i++) {
- if (nums2[i] == a) {
- left = i;
- break;
- }
- }
- // find index 2
- for (int i = nums2.length - 1; i >= 0; i--) {
- if (nums2[i] == b) {
- right = i;
- break;
- }
- }
- return new int[] {
- Math.min(left, right),
- Math.max(left, right)
- };
- }
- }
来源: http://www.bubuko.com/infodetail-2415543.html