如何提高這個leetcode解決方案的性能？

我正在解決這個 Leetcode 問題：https ://leetcode.com/problems/find-pivot-index/ 我想出了這個解決方案：

import java.util.ArrayList;
import java.util.List;

public class Solution {
    public int pivotIndex(int[] nums) {
        Integer result = null;
        List<Integer> right = new ArrayList<>(nums.length);
        List<Integer> left = new ArrayList<>(nums.length);
        int leftSum, rightSum;

        for (int i = 0; i < nums.length; i  ) {
            leftSum = 0;
            rightSum = 0;

            for (int j = 0; j < i; j  ) {
                left.add(nums[j]);
            }

            for (int num : left) {
                leftSum  = num;
            }

            for (int j = i   1; j < nums.length; j  ) {
                if (j > nums.length) {
                    right.add(0);
                } else {
                    right.add(nums[j]);
                }
            }

            for (int num : right) {
                rightSum  = num;
            }

            if (leftSum == rightSum) {
                result = i;
                return result;
            } else {
                result = -1;
                left.clear();
                right.clear();
            }
        }
        return result;
    }
}

但是我超過了時間限制......有人可以幫助我就如何讓這個運行更快一些建議嗎？
之前，我在第一個 for 回圈開始時實體化了一個新的 ArrayList 物件，因此我更改了它們的范圍，以便只發生一次實體化，并在 for 回圈結束時清除 ArrayLists。
leftSum 和 rightSum 相同，我更改了整個方法的范圍，只是在第一個 for 回圈開始時將它們的值更改為 0。我認為這兩個更改都會使其更快，但顯然沒有？
我的代碼在其他地方很慢，我現在無法檢測到它。

作為試圖準備該領域的第一次作業面試的人，任何提示/良好做法都將受到高度贊賞:)

uj5u.com熱心網友回復：

有些點有助于改進您的代碼。

1. 為什么需要新建兩個ArrayList？創建/推送元素到新的子串列需要時間。您可以從 nums[j] 計算左和右和。
2. 你不需要else阻止。只需在函式末尾回傳 -1 即可。因為如果您沒有找到任何 pivot i，則-1作為請求回傳。

代碼看起來像這樣。

public int pivotIndex(int[] nums) {
        for(int i = 0; i < nums.length; i  ) {
            int left_sum = 0;
            int right_sum = 0;
            for(int j = 0; j < i; j  ) left_sum  = nums[j];
            for(int j = i 1; j < nums.length; j  ) right_sum  = nums[j];
            if (left_sum == right_sum) return i;
        }
        return -1;
    }

uj5u.com熱心網友回復：

嘗試這個。

沒有嵌套回圈，所以這是O(n).

public static int pivotIndex(int[] nums) {
    int length = nums.length;
    int pivot = 0, left = 0, right = IntStream.of(nums).skip(1).sum();
    for (;;) {
        if (left == right) return pivot;
        left  = nums[pivot];
        if (  pivot >= length) break;
        right -= nums[pivot];
    }
    return -1;
}

public static void main(String[] args) {
    System.out.println(pivotIndex(new int[] {2, 1, -1}));
    System.out.println(pivotIndex(new int[] {1, -1, 3}));
    System.out.println(pivotIndex(new int[] {1, 7, 3, 6, 5, 6}));
}

輸出：

0
2
3

uj5u.com熱心網友回復：

對于任何好奇的人，我最終為此創建了另一個解決方案。

class Solution {
    public int pivotIndex(int[] nums) {
        int leftSum = 0, sum = Arrays.stream(nums).sum();

        for (int i = 0; i < nums.length; i  ) {
            if (i != 0) {
                leftSum  = nums[i - 1];
            }
            if (leftSum == sum - leftSum - nums[i]) {
                return i;
            }
        }
        return -1;
    }
}

對我來說，比其他答案更容易理解。

標籤：爪哇表现java-8

上一篇：Julia：隨機多項式分配

下一篇：當整個串列很長（10000）時，識別所有串列對的最快方法，它們的差異低于給定閾值