更詳細的講解和代碼調試演示過程，請參看視頻 如何進入google,算法面試技能全面提升指南

假設A是一個整數數組,長度為n，數組中的元素可能是重復的。設計一個算法，找到一系列下標的集合I = {i(0), i(1), i(2)….i(n)}. 使得(A[i(0)] + A[i(1)] + … A[i(n)] ) mod n = 0.例如假定A = {711, 704, 427, 995, 334, 62, 763, 98, 733, 721}, 于是I = {0,1,3}, 因為(A[0] + A[1] + A[3] ) mod 10 = 0. 請給出一個有效的算法找到滿足條件的集合I, 無論A的元素如何取值，這樣的集合總是存在的。

這是一道較為復雜的算法題，能在一個小時內完成絕非易事。我們需要解決兩個問題，第一需要證明，為何這樣的集合肯定存在，第二，集合存在，如何把它給挖掘出來。我們先證明第一個問題。

1：如果數組A中含有元素它的值是0，那么滿足條件的集合存在，這個集合就只包含元素0.

2：如果數組A只有一個元素，也就是A的長度只有1，那么A本身就是滿足條件的集合。

3：如果A包含不只一個元素，我們用歸納法來證明。假設n=k時，我們能從A中找到給定集合，使得(A[i(0)] + A[i(1)] + … A[i(n)] ) mod n = 0,那么當n=k+1時，我們從數組A中任意取出一個元素，如果被拿走的這個元素值是1，那么根據歸納法，我們可以從剩下的k個元素中，找到一個子集，子集中的元素之和能夠整除k, 把子集中的元素加上拿走的那個值為1的元素形成新的集合，這個集合之和能夠整除k+1.

如果拿走的元素值為t > 1, 剩下的元素個數為k, 那么肯定有 k > k+ 1 - t。我們從剩下的k 個元素中，隨便選出 k+1-t 個元素，在這些元素中，根據歸納法，肯定存在一個子集，使得子集元素的和能整除 k + 1 - t. 把這些子集的元素加上前面拿走的元素，那么所形成的新集合，一定能整除 k + 1

綜上，我們就證明了，這樣的集合是一定存在的，接下來我們需要考慮的是，如何找到這個集合。

我們看看，把元素逐個加總后對n求余會有什么性質： sum = (A[0] + A[1] + …. + A[j]) mod n j 由0一直增加到n-1.

在這個過程中，一定會出現下面這種情況： 存在一個 i, 0 <= i < j, 使得 (A[0]+A[1]+…+A[i]) mod n = (A[0]+A[1] + …A[j]) mod n. (*)

當上面情況出現時，我們有(A[i+1] + A[i+2] +… + A[j]) mod n = 0;

于是(A[i+1], … ,A[j]) 就是滿足條件的子集。為何(*)所描述的情況一定會發生呢？我們知道，對某個數求余，所得結果必然小于該數，因此對n求余，那么結果一定落入到1和n-1之間。

sum = (A[0] + A[1] + …. + A[j]) mod n

j 由0一直增加到n-1, 也就是上面的計算最多會進行n 次，得到n個求余的結果，然而求余的結果最多只可能有n-1中不同情況，那么n個結果中，肯定得有出現重復的時候，一旦出現重復的時候，(*)所描述的情況就出現了。

根據上面算法原理，我們可以實現如下代碼：

在for循環中，我們把數組A的元素逐個相加，然后對長度n求余，所得結果記為t，然后拿這個結果到另一個校驗數組B中檢驗一下，如果B[t] 的值是1，這表明(*)所描述的情況出現了，此時我們再遍歷以便(A[0]….A[j]) 把i找出來,找到i的辦法就是再次將元素逐個相加，當所得結果對n求余后，與前面算得的t相等，那么此時的元素下標i滿足條件，找到i之后，再把下標0到i從集合中去除，那么集合中剩下的下標就是對應自己中的元素在原數組中的下標。

我們再看看主入口函數的實現：

上面代碼運行后結果為： sub set is: 1 2 3 4 也就是說(A[1] + A[2] + A[3] + A[4]) mod 10 = 0, 大家可以自己檢測一下，所得結果確實是正確的。

更多技術信息，包括操作系統，編譯器，面試算法，機器學習，人工智能，請關照我的公眾號：