Java面試題——陣列求和統計-有解無憂

牛牛有兩個長度為nn的陣列a, ba,b，牛牛希望統計有多少數對(l, r)(l,r)滿足：

1，0<=l<=r<=n-1

2，sum_{i= l}^{r}{a_i} = b_l + b_r∑i=lra**i=b**l+b**r

示例1

輸入

 [1,2,3,4],[2,1,4,5]

輸出

說明

 滿足條件的數對有(0, 1), (0, 2), (1, 1), (1, 2)(0,1),(0,2),(1,1),(1,2)

示例2

輸入

 [0,0,1,1,1],[2,0,4,3,3]

輸出

1，結題思路

不使用暴力破解，因為會超時！如果想更快的解決這個問題，需要對于問題進行轉換；主要是這個公式：圖片說明這個公式比較難求解在具有兩個變數：l與r，雙份變數，雙份難度！因此最好整成一個變數，那怎么辦？舉個例子

 ?
 要求解 1+2+3+4+5+6  中第三個數字3到最后一個數字6之間的和可以怎么求？
 （1+2+3+4+5+6） - （1+2+3） + 3
 有人說，那這樣不是很繁瑣？？？對的，但是這樣我們發現公式中的變數只剩下一個，即r或者l，怎么說
 我們令S(i)表示陣列A從0->i位置上的所有資料的和，則：
 s(6) = （1+2+3+4+5+6）
 S(3) = （1+2+3）
 原來的式子就可以表示為：
 S(6) - S(3) + A[3]
 因此，我們只需要考慮如何求解S中的每個值即可

回傳到原式中，可以根據上述描述將式子轉換為：圖片說明進一步調整兩邊的變數，得到最終的結果設sumArray[i]為陣列a中從位置0到位置i上的所有元素之和，則上述式子可以表述為

$圖片說明$

求解陣列sumArray則相對來說比較簡單了，具體的代碼如下：

2，完整代碼

 import java.util.*;
  
  
 public class Solution {
     /**
      * 計算有多少對符合條件的數對
      * @param a int整型一維陣列 陣列a
      * @param b int整型一維陣列 陣列b
      * @return int整型
      */
     public int countLR (int[] a, int[] b) {
         // write code here
         int result = 0;
         int sumArray[] = new int[a.length];
         sumArray[0] = a[0];
  
         for(int i = 1; i <a.length; i++)
             sumArray[i] = sumArray[i-1] + a[i];
  
  
         for(int l = 0; l < a.length; l++)
             for(int r = l; r <b.length; r++)
                 if(sumArray[r] - b[r] == sumArray[l] - a[l] + b[l])
                     result++;
  
         return result;
     }
 }

最后的最后，上點干貨，（但凡有個這樣的女朋友，我會熬夜么？）

最后我把我收集的各大廠經典高頻面試題和Java高級進階、架構師視頻教程送予大家，部分資料如下圖所示：

獲取地址：java進階學習資料，面試題，電子書籍免費獲取

轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/96344.html

標籤：Java

上一篇：Java不可不知的泛型使用

下一篇：2019年騰訊PHP程式員面試題目分享