找到給定整數的不同三元組和的數量

您已獲得一個隨機整數陣列/串列（ARR）和一個數字 X。查找并回傳陣列/串列中不同三元組的數量，總和為 X。

我寫了這段代碼：

public class Solution { 
    public static void merge(int arr[], int lb, int mid, int ub) {
        int n1 = mid - lb   1;
        int n2 = ub - mid;
 
        int arr1[] = new int[n1];
        int arr2[] = new int[n2];
 
        for (int i = 0; i < n1; i  )
            arr1[i] = arr[lb   i];

        for (int j = 0; j < n2; j  )
            arr2[j] = arr[mid   1   j];
 
        int i = 0, j = 0;
 
        int k = lb;
        while (i < n1 && j < n2) {
            if (arr1[i] <= arr2[j])
                arr[k] = arr1[i  ];
            else
                arr[k] = arr2[j  ];

            k  ;
        }
 
        while (i < n1)
            arr[k  ] = arr1[i  ];
 
        while (j < n2)
            arr[k  ] = arr2[j  ];
    }
    
    public static void mergeSort(int arr[], int lb, int ub) {
        if (lb < ub) {
            int mid = lb   (ub - lb) / 2;
 
            mergeSort(arr, lb, mid);
            mergeSort(arr, mid   1, ub);
            merge(arr, lb, mid, ub);
        }
    }

    public static int tripletSum(int[] arr, int num) {
        mergeSort(arr, 0, arr.length - 1); 
        int n = arr.length;
        int count = 0;
        
        for (int i = 0; i < n - 2; i  ) {
            int sum = num - arr[i];
            
            int j = i   1;
            int k = n - 1;
            while (j < k) {
                if (arr[j]   arr[k] == sum) {
                    count  ;
                    k--;
                } else if (arr[j]   arr[k] > sum) {
                    k--;
                } else
                    j  ;
            }
        }

        return count;
    }
}

輸入陣列是 -1 3 3 3 3 3 3

輸入數 =9

生成的輸出 -10

預期產出 -20

幫我解決這個問題我試圖找到解決方案好幾個小時。此外，程式的時間復雜度不應超過 O(n2)。

uj5u.com熱心網友回復：

我是這樣做的，希望我能很好地理解它。

public static int tripletSum(int[] arr, int num) {
    int loops = 0; // just to check the quality of the code
    int counter = 0;
    for (int i1 = 0; i1 < arr.length - 2; i1  ) {
        for (int i2 = i1   1; i2 < arr.length - 1; i2  ) {
            for (int i3 = i2   1; i3 < arr.length; i3  ) {
                loops  ;
                if (arr[i1]   arr[i2]   arr[i3] == num) {
                    counter  ;
                }
            }
        }
    }
    // Check for not exceeding O(n^2)
    if (loops <= arr.length * arr.length) {
        System.io.println("Well done");
    } else {
        System.io.println("Too many cycles");
    }
    return counter;
}

我在陣列上從“左”到“右”迭代，并且越來越多地向“右”走。

1st, 2nd, 3rd
1st, 2nd, 4th
...
1st, 2nd, nth
2nd, 3rd, 4th
2nd, 3rd, 5th
...
2nd, 3rd, nth
.
.
.
nth - 2, nth - 1, nth

我迭代了 35 次，但可以迭代 7^2 = 49 次 --> “干得好”

uj5u.com熱心網友回復：

你錯過了一個回圈。固定代碼：

    public static int tripletSum(int[] arr, int num) {
    //Your code goes here
    mergeSort(arr, 0, arr.length - 1);
    int n = arr.length;
    int count = 0;

    for (int i = 0; i < n - 2; i  ) {
        int sum = num - arr[i];
        
        for (int j = i 1; j < n-1; j  ) {
            int k = n-1;
            while (j < k) {
                if (arr[j]   arr[k] == sum) {
                    count  ;
                    k--;
                } else if (arr[j]   arr[k] > sum) {
                    k--;
                } else {
                    j  ;
                }
            }
        }
    }
    return count;
}

uj5u.com熱心網友回復：

好的，然后優化版本：

public static int tripletSum(int[] arr, int num) {
    //Your code goes here
    mergeSort(arr, 0, arr.length - 1);
    int n = arr.length;
    int count = 0;
    for (int i = 0; i < n - 2; i  ) {
        int sum = num - arr[i];

        int maxK = n - 1;
        for (int j = i   1; j < n - 1; j  ) {
            int k = maxK;

            while (j < k) {
                if (arr[j]   arr[k] == sum) {
                    count  ;
                    k--;
                } else if (arr[j]   arr[k] > sum) {
                    k--;
                    maxK--;
                } else {
                    j  ;
                }
            }
        }
    }
    return count;
}

uj5u.com熱心網友回復：

給定的代碼適用于所有測驗用例。

import java.util.Arrays;

公共類解決方案{

public static int tripletSum(int[] arr, int num) {
    Arrays.sort(arr);
    int n = arr.length;
    
    int Numtripletsum = 0;
    for(int i=0;i<n;i  )
    {
        int pairSumFor = num - arr[i];
        int numPairs = pairSum(arr, (i 1), (n-1), pairSumFor);
        Numtripletsum =numPairs;
    }
    return Numtripletsum;
    
}
private static int pairSum(int[] arr, int startIndex, int endIndex, int num ){
    
    int numPair = 0;
    while(startIndex < endIndex){
        if(arr[startIndex]   arr[endIndex] < num){
            startIndex  ;
        }
        else if(arr[startIndex]   arr[endIndex] > num){
            endIndex--;
        }
        else
        {
            int elementAtStart = arr[startIndex];
            int elementAtEnd = arr[endIndex];
            
            if(elementAtStart == elementAtEnd){
                int totalElementsFromStartToEnd = (endIndex - startIndex)   1;
                numPair  = (totalElementsFromStartToEnd * (totalElementsFromStartToEnd -1) /2);
                
                return numPair;
            }
            int tempStartIndex = startIndex   1;
            int tempEndIndex = endIndex - 1;
            
            while(tempStartIndex <= tempEndIndex && arr[tempStartIndex] == elementAtStart){
                tempStartIndex =1;
            }
            while(tempEndIndex >= tempStartIndex && arr[tempEndIndex] == elementAtEnd){
                tempEndIndex-=1;
            }
            int totalElementsFromStart = (tempStartIndex - startIndex);
            int totalElementsFromEnd = (endIndex - tempEndIndex);
            
            numPair  = (totalElementsFromStart * totalElementsFromEnd);
            
            startIndex = tempStartIndex;
            endIndex = tempEndIndex;
        }
    }
    return numPair;
}

}

標籤：爪哇数组排序

上一篇：回傳一個有序的JSONB嵌套哈希

下一篇：基于與其他串列的交集對串列進行部分排序