给定一个整型数组,以及一个目标数值V,要求返回两个能够相对等于V值的两个数字的索引序列。每个数字只能使用一次。
例子:
`
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
`
方案:暴力运算
1 2 3 4 5 6 7 8 9 10 11 12 13
| class Solution { public int[] twoSum(int[] nums, int target) { if(nums.length < 2) return null; for(int i=0;i<nums.length;++i){ for(int j=i+1;j<nums.length;++j){ if((nums[i] + nums[j]) == target){ return new int[]{i,j}; } } } return null; } }
|
时间复杂度O(n*n),空间复杂度O(n)
扩展方案:带索引
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
| class Solution { public int[] twoSum(int[] nums, int target) { Map<Integer,Integer> indexMap = new HashMap<Integer,Integer>(); for(int i=0;i<nums.length;++i){ indexMap.put(nums[i],i); }
for(int i=0;i<nums.length;++i){ Integer idx = indexMap.get(target-nums[i]); if(idx != null && i != idx){ return new int[]{i,idx}; } } return null; } }
|
时间复杂度O(n),空间复杂度O(n)
注:该种方法有一定问题,前提需要加强条件:序列中没有重复的数字。不然该indexMap会被冲突覆盖
如:
Input: [0,4,3,0] 0
Output:null
Expected: [0,3]
原文地址:https://leetcode.com/problems/two-sum/description/