問題1
數(shù)組里求兩數(shù)之和等于目標數(shù)
原理
- 這個問題可能是很多人接觸LeetCode的第一道算法題了
- 解法很多種我還是喜歡使用map的方式來解決，map的key記錄的是數(shù)據(jù)的元素，value記錄的是數(shù)組元素對應的坐標
- 關(guān)鍵步驟在于 map.get(target-nums[i])!=null 說明找到元素
代碼
class Solution {
public int[] twoSum(int[] nums, int target) {
if(nums==null||nums.length<=0){
return null;
}
Map<Integer,Integer> map = new HashMap<>();
for(int i=0;i<nums.length;i++){
if (map.get(target-nums[i])!=null){
return new int[]{map.get(target-nums[i]),i};
}else{
map.put(nums[i],i);
}
}
return null;
}
}
注意事項
- 暫無
問題2
數(shù)組里求三數(shù)之和等于目標數(shù)
原理
- 三數(shù)之和伴郁，簡單理解就是兩數(shù)之和的進階版唧瘾，但是昨晚就完全不一樣了失息。
- 第一步髓涯，對數(shù)組進行排序 arrays.sort
- 第二步杂数，使用遍歷＋二分查找的方式奋单，搜索符合目標的元素锉试。
- 注意兩種特殊情況處理
代碼
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> list = new ArrayList<>();
if (nums == null || nums.length <= 0) {
return list;
}
Arrays.sort(nums);
for (int i = 0; i < nums.length-2; i++) {
if (i - 1 >=0 && nums[i] == nums[i - 1]) {
continue;
}
int low = i + 1;
int high = nums.length - 1;
while (low < high) {
int c = nums[i] + nums[low] + nums[high];
if (c == 0) {
List<Integer> tlist = new ArrayList<>();
tlist.add(nums[i]);
tlist.add(nums[low]);
tlist.add(nums[high]);
list.add(new ArrayList<>(tlist));
while (low < high && nums[low] == nums[low + 1]) {
low++;
}
while (low < high && nums[high] == nums[high - 1]) {
high--;
}
low++;
high--;
} else if (c < 0) {
low++;
} else {
high--;
}
}
}
return list;
}
}
注意事項
- 特別注意當i>=0 && nums[i] == nums[i - 1]這種重復的情況
- 注意排除掉第二種重復的情況 while (low < high && nums[low] == nums[low + 1]) 和
while (low < high && nums[high] == nums[high - 1])
問題3
數(shù)組里求四數(shù)之和等于目標數(shù)
原理
- 原理和三數(shù)之和類似，只是多了一層循環(huán)而已览濒，還是使用循環(huán)加雙指針
- 需要特別注意邊界問題
代碼
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> list = new ArrayList<>();
if (nums==null||nums.length<=0){
return list;
}
Arrays.sort(nums);
for(int i=0;i<nums.length;i++){
if (i>0&&nums[i]==nums[i-1]){
continue;
}
for(int j=i+1;j<nums.length;j++){
if (j>i+1&&nums[j]==nums[j-1]){
continue;
}
int low = j+1;
int high = nums.length-1;
while (low<high){
int c = nums[i]+nums[j]+nums[low]+nums[high];
if (c==target){
List<Integer> tlist = new ArrayList<>();
tlist.add(nums[i]);
tlist.add(nums[j]);
tlist.add(nums[low]);
tlist.add(nums[high]);
list.add(new ArrayList<>(tlist));
while (low<high&&nums[low]==nums[low+1]){
low++;
}
while (low<high&&nums[high]==nums[high-1]){
high--;
}
low++;
high--;
}else if(c<0){
low++;
}else{
high--;
}
}
}
}
return list;
}
}
注意事項
- 注意第一層循環(huán)的邊界問題i>0時 nums[i]==nums[i-1]
- 注意第二層循環(huán)的邊界問題j>i+1時 nums[j]==nums[j+1]
問題4
給定一個包括 n 個整數(shù)的數(shù)組 nums 和 一個目標值 target呆盖。找出 nums 中的三個整數(shù)，使得它們的和與 target 最接近贷笛。返回這三個數(shù)的和应又。假定每組輸入只存在唯一答案。
原理
- 從三數(shù)之和到四數(shù)之和再到現(xiàn)在最近的三數(shù)之和乏苦，其實原理都一樣株扛，排序＋雙指針
- 需要注意的是最近的三數(shù)之和尤筐，就需要有一個臨時遍歷記錄最接近的值
- 雙指針什么時候移動呢？當前的三數(shù)之和和目標數(shù)比較洞就，小的時候low++,大的時候high--
代碼
class Solution {
public int threeSumClosest(int[] nums, int target) {
if(nums==null||nums.length<=0){
return -1;
}
Arrays.sort(nums);
int c = Integer.MAX_VALUE;
for(int i=0;i<nums.length;i++){
int low = i+1;
int high = nums.length-1;
while(low<high){
int t = nums[low]+nums[high]+nums[i];
if(target==t){
return t;
}
if(Math.abs(t-target)-Math.abs(c-target)<0){
c = t;
}
if(t<target){
low++;
}else{
high--;
}
}
}
return c;
}
}
注意事項
- 需要注意的什么時候移動low和high
