最小尺寸子阵萨姆与排序

给定的n的正整数和正整数s的阵列，找到一个子阵列，其总和≥S的最小长度。如果没有，则返回0。

例如，给定数组[2,3,1,2,4,3]和s = 7, 子问题[4,3]在问题约束下具有最小长度。

以下是我的解决方案：

public int minSubArrayLen(int s, int[] nums) { 

    long sum = 0; 
    int a = 0; 
    if (nums.length < 1) 
     return 0; 
    Arrays.sort(nums); 

    for (int i = nums.length-1; i >= 0; i--) { 
     sum += nums[i]; 
     a++; 
     if (sum>=s) 
      break; 
    } 

    if (sum < s) { 
     return 0; 
    } 

    return a; 
}

这个解决方案，因为它没有通过下面的测试情况下不被接受：

[5334,6299,4199,9663， 8945,3566,9509,3124,6026,6250,7475,5420,9201,9501,38,5897,4411,6638,9845,161,9563,8854,3731,5564,5331,4294,3275,1972,1521， 2377,3701,6462,6778,187,9778,758,550,7510,6225,8691,3666,4622,9722,8011,7247,575,5431,4777,4032,8682,5888,8047,3562,9462,6501， 7855,505,4675,6973,493,1374， 3227,1244,7364,2298,3244,8627,5102,6375,8653,1820,3857,7195,7830,4461,7821,5037,2918,4279,2791,1500,9858,6915,5156,970,1471， 5296,1688,578,7266,4182,1430,4985,5730,7941,3880,607,8776,1348,2974,1094,6733,5177,4975,5421,8190,8255,9112,8651,2797,335， 8677,3754,893,1818,8479,5875,1695,8295,7993,7037,8546,7906,4102,7279,1407,2462,4425,2148,2925,3903,5447,5893,3534,3663,8307， 8679,8474,1202,3474,2961,1149,7451,4279,7875,5692,6186,8109,7763,7798,2250,2969,7974,9781,7741,4914,5446,1861,8914,2544,5683， 8952,6745,4870,1848,7887,6448,7873,128,3281,794,1965,7036,8094,1211,9450,6981,4244,2418,8610,8681,2402,2904,7712,3252,5029， 3004,5526,6965,8866,2764,600,631,9075,2631,3411,2737,2328,652,494,6556,9391,4517,8934,8892,4561,9331,1386,4636,9627,5435,9272,110,413， 9706,5470,5008,1706,7045,9648,7505,6968,7509,3120,7869,6776,6434,7994,5441,288,492,1617,3274,7019,5575,6664,6056,7069,1996,9581， 3103,9266,2554,7471,4251,4320,4749,649,2617,3018,4332,415,2243,1924,69,5902,3602,2925,6542,345,4657,9034,8977,6799,8397， 1187,3678,4921,6518,851,6941,6920,259,4503,2637,7438,3893,5042,8552,6661,5043,9555,9095,4123,142,1446,8047,6234,1199,8848， 5656,1910,3430,2843,8043,9156,7838,2332,9634,2410,2958,3431,4270,1420,4227,7712,6648,1607,1575,3741,1493,7770,3018,5398,6215， 8601,6244,7551,2587,2254,3607,1147,5184,9173,8680,8610,1597,1763,7914,3441,7006,1318,7044,7267,8206,9684,4814,9748,4497,2239]

预期的答案是132，但我的输出为80

没有人有任何想法出了什么毛病我的算法/代码？

来源

2016-12-02 Nicole Chen

你的代码中最大的问题是你正在采取一些线性的方式。那就是你拿前3或前5的和来确定sum是否大于s。你需要考虑你是否随机抽取这些数字，并将总和接近于s – Acewin

我会简单地解释这个安全漏洞存在的逻辑，而给予正确的逻辑来处理问题的陈述

您正在以特定的顺序号码，然后将它们进行比较。很容易，这种情况可能会有所不同，您可以随机选择数字以获得确切的总和。

例如[2,3,1,2,4,3]和s = 7

基于你逻辑步骤1->排序的数字，你会得到[1,2,2， 3,3,4] 步骤2->您选择最后2个号码（3,4）以获得您的金额7

让我们将总数更改为8 从步骤2→您得到3 + 3 + 4 = 10所以你摆脱了循环。在这一步之后，你返回一个= 2

这里的缺陷是4 + 3 + 1也会让你的逻辑跳过8个东西。同样的方法3 + 3 + 2也是可能的解决方案实现8.

排序数组是逻辑本身的第一个缺陷。如果您考虑现有安排的子阵列，排序会改变安排，因此您永远无法获得预期的解决方案。

来源

2016-12-02 00:51:11 Acewin

最小尺寸子阵萨姆与排序

回答

相关问题