兩數之和 簡單題

思路：一個Map，key是數值，value是該數值對應的下標，遍歷的時候判斷一下當前數組下標對應的值在map里有沒有可組合成target的（具體體現為在map里找target-nums【i】)，如果有，直接返回，沒有的話就加進去，繼續找。

需要掌握的方法：map的get和containsKey

cl
ass Solution {public int[] twoSum(int[] nums, int target) {Map<Integer,Integer> m = new HashMap<>();m.put(nums[0],0);for(int i = 1;i<nums.length;++i){if(m.containsKey(target - nums[i])){return new int[]{m.get(target-nums[i]),i};}else{m.put(nums[i],i);}}return new int[0];}
}

三數之和 雙指針 中等題

思路：嚴格上來說算三個指針，一個i是維護當前遍歷到的數字下標，之后的l和r指針是從i所處位置開始，在i + 1 到len - 1這個區間中尋找nums[i]的相反數。

class Solution {// -4 -1 -1 0 1 2 // public List<List<Integer>> threeSum(int[] nums) {List<List<Integer>> res = new ArrayList<>();Arrays.sort(nums);int len = nums.length;if(len < 2){return res;}for(int i = 0;i < len;++i){int l = i + 1;int r = len - 1;if( i != 0 && nums[i] == nums[i-1]){//與前一個數重復需要調過，不然會出現重復的三元組continue;}while(l < r){if(nums[i] + nums[l] + nums[r] == 0){if(l > i + 1 && nums[l] == nums[l-1] ){//這里也是同理l ++ ;continue;}List<Integer> tmp = new ArrayList<>();tmp.add(nums[i]);tmp.add(nums[l]);tmp.add(nums[r]);l++;r--;//左右指針都要變，因為l變大的話，還希望結果有可能為0，r必須變小（意味著nums[r]變小)res.add(tmp);}else if(nums[i] + nums[l] + nums[r] < 0){//nums[l] 太小了，把它變大一點l ++;}   else{r --;}}}return res;}
}