g****s
发帖数: 1755 | 1 抱歉，是我理解错了；
如果整个数列可以随意arrange的话，需要O(n^2)；
即需要要计算任意组合的sum值。需要用到Combination的算法。
import java.util.HashSet;
import java.util.Scanner;
public class PartitionProblem {
public static void main(String[] args){
//int[] array = creatArray();
int[] array = {1,2,2,3,5,7};
boolean PN = partitionPro(array);
if(PN) System.out.println("yes!");
else System.out.println("Nope.");
}//end main()
private static boolean partitionPro(int[] array) {
// TODO Auto-generated method stub
int totalSum = 0;
HashSet su... 阅读全帖 |
|
j*****8
发帖数: 3635 | 2 继续加
if currSum < 0 then currSum = 0
else if currSum >= target && currSum > curMax then currMax = currSum
没仔细想，可能不对 |
|
h***n
发帖数: 276 | 3 use another array to store currsum's indices to represent sorted currsum
in your case, currsum[2] would have a lower index than currsum[0] |
|
h***n
发帖数: 276 | 4 1) sort currsum array O(nlogn)
2) for each currsum[i], binary search the nearest number to currsum[i]+t (lo
gn) for each
to sum up O(nlogn) |
|
b*****n
发帖数: 143 | 5 Thank you for your reply. But there is one problem in this solution:
Suppose when you search currsum[2]+t, the closest element is currsum[0],
then that means the sum of sub-array from 0 to 2 is -t, not t, right? |
|
d**********6
发帖数: 4434 | 6 有点麻烦了
hash的时候直接这样
currSum = sum(nums[:i+1])
Hash(y-currSum) = i
如果遇到重复hashkey, i取较大的
这样就把2sum的hash步骤提上来，一部到位
1] |
|
j*****8
发帖数: 3635 | 7 这个有啥tricky的地方吗，难道不是加个condition check currSum >= target 就行？ |
|
