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:
Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a ≤ b ≤ c ≤ d)
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)
3sum的扩展
Note:
Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a ≤ b ≤ c ≤ d)
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)
3sum的扩展
public List<List<Integer>> fourSum(int[] num, int target) { List<List<Integer>> result = new ArrayList<List<Integer>>(); if (num == null || num.length < 4) { return result; } int temp = Integer.MAX_VALUE; Arrays.sort(num); for (int i = 0; i < num.length - 3; i++) { int tar3 = target - num[i]; while (temp == tar3 && i < num.length - 3) { i++; tar3 = target - num[i]; } List<List<Integer>> res3 = threeSum(num, tar3, i + 1, num.length - 1); for (List<Integer> ls : res3) { ls.add(0, num[i]); result.add(ls); } temp = tar3; } return result; } public List<List<Integer>> threeSum(int[] num, int target, int begin, int end) { List<List<Integer>> result = new ArrayList<List<Integer>>(); int temp = Integer.MAX_VALUE; for (int i = begin; i < end; i++) { int tar = target - num[i]; while (temp == tar && i < end) { i++; tar = target - num[i]; } int less = i + 1; int over = end; while (less < over) { if (tar > num[less] + num[over]) { less++; while (num[less] == num[less - 1] && less < over) { less++; } } else if (tar < num[less] + num[over]) { over--; while (num[over] == num[over + 1] && over > less) { over--; } } else { int[] c = { num[i], num[less], num[over] }; List<Integer> temp1 = new ArrayList<Integer>(); for (int k : c) { temp1.add(k); } result.add(temp1); over--; while (num[over] == num[over + 1] && over > less) { over--; } less++; while (num[less] == num[less - 1] && less < over) { less++; } } } temp = tar; } return result; }
发表评论
-
Merge k Sorted Lists
2015-03-12 19:55 325Merge k sorted linked lists and ... -
Generate Parentheses
2015-03-12 19:50 363Given n pairs of parentheses, w ... -
Generate Parentheses
2015-03-05 22:39 0Given n pairs of parentheses, w ... -
Valid Parentheses
2015-03-05 22:33 307Given a string containing just ... -
Remove Nth Node From End of List
2015-03-05 22:31 339Given a linked list, remove the ... -
Letter Combinations of a Phone Number
2015-03-05 22:30 330Letter Combinations of a Phone ... -
3Sum Closest
2015-03-05 22:25 291Given an array S of n integers, ... -
3Sum
2015-03-03 22:34 317Given an array S of n integers, ... -
Longest Common Prefix
2015-03-03 22:21 327Write a function to find the lo ... -
Roman to Integer
2015-03-03 22:20 326Given a roman numeral, convert ... -
Integer to Roman
2015-03-01 23:35 289Given an integer, convert it to ... -
Container With Most Water
2015-03-01 22:55 321Given n non-negative integers a ... -
Regular Expression Matching
2015-03-01 20:19 366Implement regular expression ma ... -
Palindrome Number
2015-02-13 22:08 330Determine whether an integer is ... -
String to Integer (atoi)
2015-02-13 11:07 340Implement atoi to convert a str ... -
Reverse Integer
2015-02-12 23:39 227Reverse digits of an integer. ... -
ZigZag Conversion
2015-02-12 23:37 254The string "PAYPALISHIRING ... -
Longest Palindromic Substring
2015-02-12 22:50 333Given a string S, find the long ... -
Add Two Numbers
2015-02-12 22:12 299You are given two linked lists ... -
Longest Substring Without Repeating Characters
2015-02-11 21:14 425[size=24px;]Longest Substring W ...
相关推荐
双指针算法,python数组双指针算法求和问题LeetCode2sum3sum4sum含代码
文档python数组双指针算法求和问题LeetCode2sum3sum4sum含代码提取方式是百度网盘分享地址
此算法解决如下问题:给定数据数均为n(1≦n≦4000)的四张数据表A、B、C、D,数据类型为整型,试从每张表中选出一个数,使得四个数的和为0,问这样的组合共有多少?
sum(2,3,4)和sum(2)(3)(4)输出值一样
For example, if t=4, n=6, and the list is [4,3,2,2,1,1], then there are four different sums that equal 4: 4,3+1,2+2, and 2+1+1.(A number can be used within a sum as many times as it appears in the ...
17 4Sum 55 18 3Sum Closest 57 19 String to Integer (atoi) 59 20 Merge Sorted Array 61 ... ... 231 Counting Bits 561 232 Maximum Product of Word Lengths 563 233 Gray Code 565 234 Permutations 567 235 ...
18. 4Sum 19. Remove Nth Node From End of List 20. Valid Parentheses 21. Merge Two Sorted Lists 22. Generate Parentheses 23. Merge k Sorted Lists 24. Swap Nodes in Pairs 25. Reverse Nodes in k-Group 26...
18| [4 Sum](https://leetcode.com/problems/4sum/) | [C++](./C++/4sum.cpp) [Python](./Python/4sum.py) | _O(n^3)_ | _O(1)_ | Medium || Two Pointers 26 | [Remove Duplicates from Sorted Array]...
Public Function tx_read_frame(leixing As Byte, data1 As Byte, data2 As Byte, data3 As Byte, data4 As Byte) Static Byteout(0 To 7) As Byte, i As Byte '向外发送 Dim sum As Integer Byteout(0) = &H55; ...
matlab函数sum和size用法-matlab函数sum和size用法.doc matlab函数sum和size用法.doc sum函数解释函数功能 求数组元素的总和 使用方法B = sum 返回数组A不同维数的总和。 如果A是一个...
Multiplicate_4_4 num1_1 Position_adc_ctrl Position_Adjust pulse_16 pulse_16_sum pulse_sum Rate_Adjust Rate_Measure ROM_3_4 RS_FF second_pulse_latch Serial Shift_Latch SRAM_8_8 stopwatch subtracter_1 ...
ERP迁移至S4HANA 第五步: Technical conversion with SUM(DMO)
ZEROSUM鳞波X4ZEROSUMチヌX4PWZEROSUM鳞-宇崎日新.pdf
Calculating The Sum of Its Parts 数据结构,树的一道题。
4总和 Leetcode 问题 18 给定一个由 n 个整数组成的数组 nums 和一个整数目标,nums 中是否有元素 a、b、c 和 d 使得 a + b + c + d = target? 找到数组中所有唯一的四元组,给出目标的总和。 笔记: The solution ...
4Sum Remove Element Move Zeroes Next Permutation Permutation Sequence Valid Sudoku Trapping Rain Water Rotate Image Plus One Climbing Stairs Set Matrix Zeroes Gas Station Candy Majority Element Rotate...
第4章 集成运算放大器及其应用SUM4.pptx
http://www.centospub.com/make/install.html这个页面上的md5sum下载地址无法下载。 http://mirror.tini4u.net/centos/4.4/isos/i386/md5sum
DirectX 9.0 SDK (summer 2004)
ISO 7870-4:2011 Control charts - Part 4:Cumulative sum charts -