classSolution{publicint[]twoSum(int[]nums,inttarget){Map<Integer,Integer>map=newHashMap<>();for(inti=0;i<nums.length;i++)map.put(nums[i],i);intcomplement=0;for(inti=0;i<nums.length;i++){complement=target-nums[i];if(map.containsKey(complement)&&map.get(complement)!=i)returnnewint[]{i,map.get(complement)};}thrownewIllegalArgumentException("No two sum solution");}}
复杂度分析:11ms
时间复杂度:O(n)O(n), 我们只遍历了包含有 nn 个元素的列表一次。在表中进行的每次查找只花费 O(1)O(1) 的时间。
空间复杂度:O(n)O(n), 所需的额外空间取决于哈希表中存储的元素数量,该表最多需要存储 nn 个元素。
Other Solution
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
classSolution{intsize=2048;int[]map=newint[size];intlength=2047;intindex;publicint[]twoSum(int[]nums,inttarget){for(inti=0;i<nums.length;i++){index=nums[i]&length;if(map[index]!=0){returnnewint[]{map[index]-1,i};}else{map[(target-index)&length]=i+1;}}thrownewIllegalArgumentException("No two sum solution");}}