摘要:解題思路題目要求兩個(gè)數(shù)和等于,返回其題目說(shuō)明不會(huì)有重復(fù)情況,所以我們一旦發(fā)現(xiàn)符合情況的,就可以直接結(jié)束循環(huán)并返回。特殊情況就是正好等于,那肯定是最接近的情況,直接返回即可。
Two Sum
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution.
Example: Given nums = [2, 7, 11, 15], target = 9, Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1].
1.解題思路
題目要求兩個(gè)數(shù)和等于target,返回其index.題目說(shuō)明不會(huì)有重復(fù)情況,所以我們一旦發(fā)現(xiàn)符合情況的,就可以直接結(jié)束循環(huán)并返回。
利用HashMap
2.代碼
public class Solution { public int[] twoSum(int[] nums, int target) { int[] res=new int[2]; if(nums.length==0) return res; HashMaphm=new HashMap (); for(int i=0;i 3Sum
Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.Note: The solution set must not contain duplicate triplets.
For example, given array S = [-1, 0, 1, 2, -1, -4], A solution set is: [ [-1, 0, 1], [-1, -1, 2] ]1.解題思路
本題要求三個(gè)數(shù)的和為0,其實(shí)就是固定一個(gè)數(shù)n之后,找兩個(gè)數(shù)和為0-n,所以就轉(zhuǎn)化為求兩個(gè)數(shù)的和,那我們很容易想到使用二分法。
注意點(diǎn):本題需要排除重復(fù)值,
1)固定的數(shù)下標(biāo)為i,則要從i+1開(kāi)始尋找后兩個(gè)數(shù);
2)如果數(shù)組中包含重復(fù)的數(shù),則為了保證結(jié)果不出現(xiàn)重復(fù),我們每次遇到重復(fù)的數(shù)需要跳過(guò)。2.代碼
public class Solution { List> res =new ArrayList
>(); public List
> threeSum(int[] nums) { Arrays.sort(nums); for(int i=0;i
0&&nums[i]==nums[i-1]) continue; //避免重復(fù) twoSum(0-nums[i],nums,i+1,nums.length-1); } return res; } private void twoSum(int target,int[] nums, int start,int end){ int i=start,j=end; while(i subres=new ArrayList (); int sum=nums[i]+nums[j]; if(sum==target){ subres.add(0-target); subres.add(nums[i]); subres.add(nums[j]); res.add(subres); do { i++; }while(i < end && nums[i] == nums[i-1]); do { j--; } while(j >= 0 && nums[j] == nums[j+1]); } else if(sum 4Sum
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.Note: The solution set must not contain duplicate quadruplets.
For example, given array S = [1, 0, -1, 0, -2, 2], and target = 0. A solution set is: [ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2] ]1.解題思路
4Sum,就是在3Sum基礎(chǔ)上再嵌套一層,注意點(diǎn)也是要避免重復(fù)。
2.代碼
public class Solution { ArrayList> res = new ArrayList
>(); public List
> fourSum(int[] nums, int target) { Arrays.sort(nums); for(int i=0;i
0&&nums[i]==nums[i-1]) continue; res.addAll(threesum(target-nums[i],nums,i+1)); } return res; } private List > threesum(int target,int[] nums,int start){ ArrayList
> res = new ArrayList
>(); int first=start-1; for(int i=start;i
start&&nums[i]==nums[i-1]) continue; res.addAll(twosum(target-nums[i],nums,i+1,first)); } return res; } private List > twosum(int target,int[] nums,int start,int first){ List
> res =new ArrayList
>(); int second=start-1; int i=start; int j=nums.length-1; while(i
subres =new ArrayList (); int sum=nums[i]+nums[j]; if(sum==target){ subres.add(nums[first]); subres.add(nums[second]); subres.add(nums[i]); subres.add(nums[j]); res.add(subres); i++; while(i =0&&nums[j]==nums[j+1]){ j--; } } else if(sum>target) j--; else i++; } return res; } } 3Sum Closest
Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.For example, given array S = {-1 2 1 -4}, and target = 1. The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).1.解題思路
與3Sum相似,只不過(guò)本次是要尋找最接近target的3個(gè)數(shù)之和,我們需要維護(hù)minDiff和closetSum兩個(gè)變量。
但是本題題目說(shuō)明不許考慮重復(fù)。 特殊情況就是sum正好等于target,那肯定是最接近的情況,直接返回即可。2.代碼
public class Solution { public int threeSumClosest(int[] nums, int target) { if(nums.length==0) return 0; int minDiff=Integer.MAX_VALUE; int closet=0; Arrays.sort(nums); for(int i=0;itarget){ right--; } else return sum; } } return closet; } } 4Sum II
Given four lists A, B, C, D of integer values, compute how many tuples (i, j, k, l) there are such that A[i] + B[j] + C[k] + D[l] is zero.
To make problem a bit easier, all A, B, C, D have same length of N where 0 ≤ N ≤ 500. All integers are in the range of -228 to 228 - 1 and the result is guaranteed to be at most 231 - 1.
Example: Input: A = [ 1, 2] B = [-2,-1] C = [-1, 2] D = [ 0, 2] Output: 2 Explanation: The two tuples are: 1. (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0 2. (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 01.解題思路
本題從1個(gè)數(shù)組擴(kuò)展到了4個(gè)數(shù)組,求的是有多少組4數(shù)之和等于target的,我們把問(wèn)題分為兩個(gè)數(shù)一組,假設(shè)當(dāng)前兩個(gè)數(shù)A[i]+B[j],那我們其實(shí)就是要在C和D中求是否存在和為0-A[i]-B[j],如果存在則返回存在的個(gè)數(shù)。想到用HashMap,存儲(chǔ)
. 2.代碼
public class Solution { public int fourSumCount(int[] A, int[] B, int[] C, int[] D) { if(A.length==0||B.length==0||C.length==0||D.length==0) return 0; Mapmap=new HashMap (); int count=0; for(int i=0;i
文章版權(quán)歸作者所有,未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址:http://specialneedsforspecialkids.com/yun/76392.html
摘要:為了避免得到重復(fù)結(jié)果,我們不僅要跳過(guò)重復(fù)元素,而且要保證找的范圍要是在我們最先選定的那個(gè)數(shù)之后的。而計(jì)算則同樣是先選一個(gè)數(shù),然后再剩下的數(shù)中計(jì)算。 2Sum 在分析多數(shù)和之前,請(qǐng)先看Two Sum的詳解 3Sum 請(qǐng)參閱:https://yanjia.me/zh/2019/01/... 雙指針?lè)?復(fù)雜度 時(shí)間 O(N^2) 空間 O(1) 思路 3Sum其實(shí)可以轉(zhuǎn)化成一個(gè)2Sum的題,...
摘要:找符合條件的總數(shù)。雙指針區(qū)間考慮邊界,長(zhǎng)度,為空,等。之后的范圍用雙指針和表示。若三個(gè)指針的數(shù)字之和為,加入結(jié)果數(shù)組。不要求,所以不用判斷了。同理,頭部?jī)蓚€(gè)指針向后推移,后面建立左右指針夾逼,找到四指針和為目標(biāo)值的元素。 Two Sum Problem Given an array of integers, find two numbers such that they add up ...
摘要:前言從開(kāi)始寫(xiě)相關(guān)的博客到現(xiàn)在也蠻多篇了。而且當(dāng)時(shí)也沒(méi)有按順序?qū)懍F(xiàn)在翻起來(lái)覺(jué)得蠻亂的。可能大家看著也非常不方便。所以在這里做個(gè)索引嘻嘻。順序整理更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新 前言 從開(kāi)始寫(xiě)leetcode相關(guān)的博客到現(xiàn)在也蠻多篇了。而且當(dāng)時(shí)也沒(méi)有按順序?qū)憽F(xiàn)在翻起來(lái)覺(jué)得蠻亂的。可能大家看著也非常不方便。所以在這里做個(gè)索引嘻嘻。 順序整理 1~50 1...
摘要:和方法一樣,多一個(gè)數(shù),故多一層循環(huán)。完全一致,不再贅述, 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 ...
摘要:題目詳情輸入一個(gè)長(zhǎng)度為的整數(shù)數(shù)組和一個(gè)目標(biāo)整數(shù),我們需要找出是否存在個(gè)元素,使得的和等于。如果有,輸出這樣的非重復(fù)的元素序列。在求元素的時(shí)候可以通過(guò)左右指針減少查找時(shí)間。 題目詳情 Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target...
閱讀 3433·2021-11-22 09:34
閱讀 1899·2019-08-30 12:53
閱讀 3490·2019-08-28 18:07
閱讀 2976·2019-08-27 10:55
閱讀 2959·2019-08-26 10:12
閱讀 3584·2019-08-23 18:21
閱讀 1338·2019-08-23 14:10
閱讀 1469·2019-08-23 13:04