當前位置:網站首頁>【打卡第201道】【雙指針】【leetCode高頻】:18. 四數之和
【打卡第201道】【雙指針】【leetCode高頻】:18. 四數之和
2022-01-26 22:10:17 【CodingLJ】
1、題目描述
給你一個由 n 個整數組成的數組 nums ,和一個目標值 target 。請你找出並返回滿足下述全部條件且不重複的四元組 [nums[a], nums[b], nums[c], nums[d]] (若兩個四元組元素一一對應,則認為兩個四元組重複):
0 <= a, b, c, d < n
a、b、c 和 d 互不相同
nums[a] + nums[b] + nums[c] + nums[d] == target
你可以按 任意順序 返回答案 。
2、算法分析
這個題和前面的三數之和、最小範圍是一樣的。
使用雙循環 + 雙指針:
求數組中四個數的和,其中符合條件的組合中的和不能重複。
最重要的兩步驟:組合 + 去重
①先對數組進行排序,排序過的數組的元素更好操作
②從第一個元素 i 開始遍曆,遇到重複的就跳過
③再從i + 1開始遍曆如果遇到重複那就跳過
④接著就是雙指針,如果sum == target,那麼將結果添加到結果集中
注意轉換,Arrays.asList(nums[i],nums[j]....)注意添加
⑤在雙指針遍曆的過程中,也需要去重
關於去重:
[1,-1,-1,-1,0,2],target = 0,那麼第一個-1:[-1,-1,0,2],和第二個-1[-1,-1,0,2]其實結果都是一樣的。
3、代碼實現
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(nums);
for(int i = 0;i < nums.length - 3;i++){
if(i > 0 && nums[i] == nums[i - 1]){
continue;
}
for(int j = i + 1;j < nums.length - 2;j++){
if(j > i + 1 && nums[j] == nums[j - 1]){
continue;
}
int left = j + 1;
int right = nums.length - 1;
while(left < right){
int sum = nums[i] + nums[j] + nums[left] + nums[right];
if(sum == target){
result.add(Arrays.asList(nums[i],nums[j],nums[left],nums[right]));
// 去重
while(left < right && nums[left] == nums[left + 1]){
left++;
}
while(left < right && nums[right] == nums[right - 1]){
right--;
}
left++;
right--;
}else if(sum > target){
right--;
}else{
left++;
}
}
}
}
return result;
}
}
版權聲明
本文為[CodingLJ]所創,轉載請帶上原文鏈接,感謝
https://cht.chowdera.com/2022/01/202201262210167599.html
邊欄推薦
猜你喜歡
隨機推薦
- uniapp上傳圖片及組件傳值
- 瑞利年金險資金保障安全嗎?收益高不高啊?
- 華為手機USB連不上電腦的解决方法
- Flutter 2,移動金融應用開發
- 關於st25系列NFC標簽簡單介紹及st25TV系列用於門禁讀取時的注意事項總結
- 關於用ffmpeg轉手機視頻發現視頻長寬倒了的問題
- 函數 / 類模板--模板2
- 數組中的第k個最大的元素--優先級隊列、排序、堆、排序
- 單片機實例27——ADC0809A/D轉換器基本應用技術(硬件電路圖+匯編程序+C語言程序)
- Collection集合的學習
- 一場面試結束,某度員工從事Android 5年為何還是初級工程師?
- 3本書閱讀筆記【人月神話-Go語言實戰-研發能力持續成長路線】01
- PHP垃圾回收機制
- 【電子技術】什麼是LFSR?
- 死鎖?如何定比特到死鎖?如何修複死鎖?(jps和jstack兩個工具)
- 快樂寒假 22/01/20
- image
- 噴程序員?SURE?
- LDO分壓電阻計算小工具
- 面試之求一串字符串中每個字符的出現次數
- 【ISO15765_UDS&OBD診斷】-01-概述
- 【Mysql上分之路】第九篇:Mysql存儲引擎
- RHCE 第一次作業
- 2021.10.16我的第一篇博客:一切皆有可能!
- CTA-敏感行為-讀取IMEI
- 面試被問怎麼排查平時遇到的系統CPU飆高和頻繁GC,該怎麼回答?
- nuxt項目總結-綜合
- 自然語言處理學習筆記(一)
- C語言第一課
- 各比特大佬,Spark的重點難點系列暫時更新完畢
- 基於 esbuild 的 universal bundler 設計
- XCTFre逆向(四):insanity
- 理解什麼是真正的並發數
- JVM腦圖
- 【Pytorch(四)】學習如何使用 PyTorch 讀取並處理數據集
- 函數棧幀的創建與銷毀
- 構建神經網絡- 手寫字體識別案例
- 多模態生成模型ERNIE-VILG
- kotlin不容忽視的小細節
- 備戰一年,終於斬獲騰訊T3,我堅信成功是可以複制的