摘要:題目詳情輸入一個長度為的整數數組和一個目標整數,我們需要找出是否存在個元素,使得的和等于。如果有,輸出這樣的非重復的元素序列。在求元素的時候可以通過左右指針減少查找時間。
題目詳情
Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.想法輸入一個長度為n的整數數組和一個目標整數target,我們需要找出是否存在4個元素a、b、c、d,使得abcd的和等于target。如果有,輸出這樣的非重復的元素序列。
For example, 輸入數組S = [1, 0, -1, 0, -2, 2], 目標整數target = 0.
返回的結果集是:
[
[-1, 0, 0, 1],
[-2, -1, 1, 2],
[-2, 0, 0, 2]
]
本題的思路還是基于3Sum問題延伸出來的。
減治思想,如果通過遍歷,每次鎖定一個元素作為a元素,然后剩下的問題就變成了求三個數的和是否等于target,依次類推。
在求cd元素的時候可以通過左右指針減少查找時間。
解法public List> fourSum(int[] nums, int target) { Arrays.sort(nums); List
> res = new ArrayList
>(); int length = nums.length; if(length<4 || target > nums[length-1]*4 || target < nums[0]*4)return res; for(int i=0;i
0 && nums[i] != nums[i-1])){ for(int j=i+1;j tempTarget){ high--; }else{ low++; } } } } } } return res; }
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/70995.html
摘要:和方法一樣,多一個數,故多一層循環。完全一致,不再贅述, 4Sum Problem Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which ...
摘要:解題思路題目要求兩個數和等于,返回其題目說明不會有重復情況,所以我們一旦發現符合情況的,就可以直接結束循環并返回。特殊情況就是正好等于,那肯定是最接近的情況,直接返回即可。 Two SumGiven an array of integers, return indices of the two numbers such that they add up to a specific ta...
摘要:這里需要注意及時處理掉重復的情況。那么就需要盡可能排除不可能的情況來提高計算效率。因為數組已經被排序,所以可以根據數組中元素的位置判斷接下來的情況是否有可能合成目標值。 題目要求 此處為原題地址 Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d =...
摘要:為了避免得到重復結果,我們不僅要跳過重復元素,而且要保證找的范圍要是在我們最先選定的那個數之后的。而計算則同樣是先選一個數,然后再剩下的數中計算。 2Sum 在分析多數和之前,請先看Two Sum的詳解 3Sum 請參閱:https://yanjia.me/zh/2019/01/... 雙指針法 復雜度 時間 O(N^2) 空間 O(1) 思路 3Sum其實可以轉化成一個2Sum的題,...
摘要:前言從開始寫相關的博客到現在也蠻多篇了。而且當時也沒有按順序寫現在翻起來覺得蠻亂的。可能大家看著也非常不方便。所以在這里做個索引嘻嘻。順序整理更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新 前言 從開始寫leetcode相關的博客到現在也蠻多篇了。而且當時也沒有按順序寫~現在翻起來覺得蠻亂的。可能大家看著也非常不方便。所以在這里做個索引嘻嘻。 順序整理 1~50 1...
閱讀 3455·2023-04-26 02:31
閱讀 3621·2021-11-23 09:51
閱讀 1287·2021-11-17 09:33
閱讀 2436·2021-11-16 11:45
閱讀 2566·2021-10-11 11:12
閱讀 2406·2021-09-22 15:22
閱讀 2713·2021-09-04 16:40
閱讀 2569·2021-07-30 15:30