Tìm một cặp phần tử từ một mảng có tổng bằng một số đã cho trong javascript

Cho một mảng n số nguyên và một số targetSum, hãy viết chương trình để xác định xem có một cặp phần tử nào trong mảng có tổng bằng targetSum không

• Chúng tôi giả sử tất cả các yếu tố là khác biệt
• Giá trị trong mảng có thể âm và dương

ví dụ

Input: X[] = [-5, 1, -40, 20, 6, 8, 7 ], targetSum = 15
Output: true
Explanation: (7,8) or (-5, 20) are the pairs with sum 15.Input: X[] = [-5, 4, -2, 16, 8, 9], targetSum = 15
Output: false
Explanation: There is no pair of elements whose sum is equal to 15.

Lưu ý quan trọng. Trước khi chuyển sang các giải pháp, chúng tôi khuyên người học giải quyết vấn đề này. Nếu giải quyết được thì tốt. Chúng tôi muốn nghe ý tưởng của bạn trong bình luận. Mặt khác, không vấn đề gì, đây là cơ hội để tìm hiểu một mô hình mới trong việc giải quyết vấn đề. Suy nghĩ và tận hưởng. )

Một ý tưởng đơn giản là sử dụng hai vòng lặp lồng nhau và kiểm tra từng cặp (i, j) trong X[]. Nếu tồn tại một cặp có tổng bằng targetSum thì chúng ta trả về true, ngược lại, đến cuối cả hai vòng lặp nếu chúng ta không tìm thấy một cặp như vậy thì chúng ta trả về false

Thuật toán Mã giả

int sumPair (X[], n, targetSum)
{
    for(int i = 0, i < n; i = i + 1)
    {
        for(j = i + 1; j < n; j = j + 1)
        { 
            if(X[i] + X[j] == targetSum)
            return 1
        }
    }
    return -1
}

Phân tích độ phức tạp thời gian và không gian

Chúng tôi đang khám phá tất cả các cặp có thể có trong mảng và thực hiện các thao tác liên tục cho từng cặp. Tổng số không. số cặp có thể = nC2 = n(n-1)/2 = O(n²). Vì vậy, Độ phức tạp của thời gian = O(n²). chúng tôi đang sử dụng không gian bổ sung không đổi, Độ phức tạp của không gian = O(1). Nhưng câu hỏi quan trọng là - làm thế nào chúng ta có thể cải thiện độ phức tạp của thời gian hơn nữa?

Ý tưởng thuật toán

Một ý tưởng khác là sắp xếp mảng và với mọi giá trị X[i], áp dụng tìm kiếm nhị phân để tìm giá trị targetSum — X[i] trong mảng. Tìm kiếm nhị phân thực hiện tìm kiếm trong O(logn) có thể giúp chúng tôi cải thiện độ phức tạp về thời gian. Nếu có targetSum — X[i] thì trả về 1 nếu không thì trả về false

Các bước thuật toán

• Sắp xếp mảng X[] tăng dần
• Chạy một vòng lặp cho từng phần tử X[i], áp dụng tìm kiếm nhị phân để tìm targetSum — X[i]
• Nếu tồn tại một giá trị targetSum — X[i] trong mảng, thì trả về true
• Nếu không có cặp nào như vậy trong toàn bộ mảng thì trả về false

Thuật toán Mã giả

int sumPair (X[], n, targetSum)
{
    Sort(X, n)
    for(int i = 0; i < n; i = i + 1)
    { 
        int k = binarySearch (X, 0, n-1, targetSum - X[i])
        if (k) 
            return 1
    }
    return -1
}int binarySearch(int X[], int l, int r, int key)
{ 
    while (l <= r) 
    { 
        int mid = l + (r - l) / 2
        if (X[mid] == key) 
            return mid
        if (X[mid] < key) 
            l = mid + 1
        else
            r = mid - 1
    }
    return -1
}

Phân tích độ phức tạp thời gian và không gian

Giả sử chúng ta đang sử dụng thuật toán sắp xếp O(nlogn) hiệu quả sắp xếp đống và thực hiện tìm kiếm nhị phân lặp đi lặp lại để tìm kiếm targetSum — X[i] n lần

Độ phức tạp về thời gian = Độ phức tạp về thời gian của sắp xếp heap + n* Độ phức tạp về thời gian của tìm kiếm nhị phân = O(nlogn) + n. O(logn) = O(nlogn) + O(nlogn) = O(nlogn)

Độ phức tạp không gian = Độ phức tạp không gian của sắp xếp heap + Độ phức tạp không gian của tìm kiếm nhị phân lặp = O(1) + O(1) = O(1)

Ý tưởng thuật toán

Chúng ta có thể tối ưu hóa cách tiếp cận trên và tìm một phương pháp khác để tìm kiếm cặp trong mảng được sắp xếp không?

Sắp xếp mảng và sau đó di chuyển hai con trỏ vào trong từ cả hai đầu của mảng, tại mỗi điểm nhìn vào tổng của chúng. Nếu tổng của cặp bằng targetSum, thì chúng ta đã hoàn thành và trả về true. Nhưng nếu tổng vượt quá giá trị của targetSum, thì bất kỳ tổng nào sử dụng phần tử lớn hơn đều quá lớn, vì vậy chúng tôi di chuyển con trỏ bên phải vào trong để có tổng nhỏ hơn. Nếu tổng nhỏ hơn targetSum, thì bất kỳ tổng nào sử dụng phần tử thấp hơn đều quá nhỏ, vì vậy chúng tôi di chuyển con trỏ bên trái vào trong để có tổng lớn hơn. Đến cuối quá trình này, nếu cả hai con trỏ giao nhau, cặp không có trong mảng và chúng tôi trả về false

Các bước thuật toán

1. Sắp xếp mảng đầu vào theo thứ tự tăng dần
2. Bây giờ chúng ta khởi tạo hai con trỏ trong mảng đã sắp xếp, con trỏ bên trái l = 0 và con trỏ bên phải r = n-1
3. Chạy một vòng lặp trong khi l < r

• Nếu (X[l] + X[r] == targetSum) thì trả về true
• if( X[l] + X[r] < targetSum) sau đó tăng l lên 1
• if( X[l] + X[r] > targetSum) thì giảm r đi 1

4. Nếu không tìm thấy một cặp như vậy trong toàn bộ mảng - trả về false

Thuật toán Mã giả

int sumPair(X[], int n, int targetSum)
{ 
    Sort(X, n)
    int l = 0, r = n - 1 
    while (l < r)
    {
        if(X[l] + X[r] == targetSum)
            return 1
        else if(X[l] + X[r] < targetSum)
            l = l + 1
        else
            r = r - 1
    } 
    return -1
}

Phân tích độ phức tạp thời gian và không gian

Giả sử chúng ta đang sử dụng thuật toán sắp xếp tại chỗ O(nlogn) heap sort. Nhưng bây giờ câu hỏi quan trọng là - độ phức tạp về thời gian của vòng lặp while của cách tiếp cận hai con trỏ là bao nhiêu?

Trên cơ sở so sánh, chúng ta đang di chuyển con trỏ sang trái hoặc phải 1. Trong trường hợp xấu nhất, chúng tôi đang truy cập từng giá trị của mảng bằng hai con trỏ. Vì vậy, độ phức tạp thời gian của hai cách tiếp cận con trỏ = O(n)

Độ phức tạp thời gian tổng thể = Độ phức tạp thời gian của sắp xếp đống + Độ phức tạp thời gian của vòng lặp while = O (n log n) + O(n) = O (n log n). Độ phức tạp không gian = O(1), chúng tôi sử dụng không gian bổ sung không đổi

Ý tưởng thuật toán

Chúng tôi đã cải thiện độ phức tạp thời gian trong hai giải pháp cuối cùng, nhưng nó vẫn nằm trong phạm vi O(nlogn) do sự thống trị của thuật toán sắp xếp. Vì vậy, bây giờ câu hỏi quan trọng - làm thế nào chúng ta có thể tối ưu hóa hơn nữa để giải quyết nó bằng cách sử dụng độ phức tạp của thời gian tuyến tính? . Vì vậy, ý tưởng tốt nhất là sử dụng Bảng băm để cải thiện độ phức tạp về thời gian hơn nữa vì nó thực hiện tìm kiếm hiệu quả ở mức trung bình O(1)

Vì vậy, ý tưởng sẽ là lặp lại mảng và chèn phần tử X[i] vào bảng Hash. Trước khi chèn X[i], chúng ta kiểm tra xem targetSum — X[i] đã tồn tại trong bảng chưa. Nếu nó tồn tại, chúng tôi đã tìm thấy một cặp có tổng bằng targetSum và chúng tôi trả về true

Các bước thuật toán

• Lấy một Bảng băm có kích thước bằng n
• Chạy một vòng lặp và quét qua mảng X[] cho mỗi X[i]. Kiểm tra xem targetSum — X[i] có trong bảng băm hay không. Nếu có, chúng tôi đã tìm thấy cặp và trả về true. Nếu không thì chèn X[i] vào bảng Hash
• Nếu chúng tôi không tìm thấy một cặp như vậy ở cuối vòng lặp thì hãy trả về false

Thuật toán Mã giả

bool sumPair(int X[], int n, int targetSum) 
{ 
    Hash Table H
    for (i = 0; i < n; i = i + 1)
    { 
        int k = targetSum - X[i]
        if (H.search(k)) 
            return 1
        H.insert(X[i])
    } 
    return -1
}

Phân tích độ phức tạp thời gian và không gian

Trong trường hợp xấu nhất, chúng tôi quét toàn bộ mảng và không tìm thấy bất kỳ cặp nào như vậy. Tìm kiếm và chèn vào bảng băm là các hoạt động quan trọng

Độ phức tạp về thời gian = Độ phức tạp về thời gian của việc chèn n phần tử vào bảng băm + Độ phức tạp về thời gian khi tìm kiếm targetSum — X[i] n lần vào bảng băm = n. O(1) + n. O(1) = O(n) + O(n) = O(n)

Độ phức tạp không gian = O(n), chúng tôi đang sử dụng bảng băm có kích thước O(n)

Lưu ý quan trọng. Chúng tôi khuyến nghị người học chuyển đổi các đoạn mã giả trên sang một ngôn ngữ lập trình yêu thích (C, C++, Java, Python, v.v. ) và xác minh tất cả các trường hợp thử nghiệm. Vui lòng cho chúng tôi biết nếu bạn tìm thấy bất kỳ lỗi hoặc lỗi nào; . Thích lập trình

Các câu hỏi có thể có của Người phỏng vấn. Ý tưởng để suy nghĩ

• Có cách nào khác để giải quyết vấn đề này không?
• Trong cách tiếp cận cuối cùng, độ phức tạp về thời gian và không gian sẽ là bao nhiêu nếu chúng ta sử dụng BST thay cho bảng băm?
• Trong cách tiếp cận thứ 2 và thứ 3, độ phức tạp về thời gian và không gian sẽ như thế nào nếu chúng ta sử dụng quicksort?
• Tất cả các thuật toán trên có hoạt động tốt nếu các phần tử được lặp lại không?
• Tại sao ý tưởng về cách tiếp cận hai con trỏ hoạt động hoàn hảo cho một mảng được sắp xếp?
• Trong tất cả các cách tiếp cận trên, chúng ta có cần xử lý riêng trường hợp cho các giá trị âm không?
• Làm thế nào chúng tôi sửa đổi mã trên nếu chúng tôi cần trả về một cặp với targetSum?
• Làm thế nào chúng tôi sửa đổi mã trên nếu chúng tôi cần đếm tất cả các cặp với targetSum?

So sánh độ phức tạp của thời gian và không gian

• Hai vòng lồng nhau. Thời gian = O(n²), Không gian = O(1)
• Sắp xếp và tìm kiếm nhị phân. Thời gian = O(nlogn), Không gian = O(1)
• Sắp xếp và hai con trỏ. Thời gian = O(nlogn), Không gian = O(1)
• Bảng băm. Thời gian = O(n), Không gian = O(n)

Đề xuất câu hỏi mã hóa để thực hành

• Bẫy nước mưa
• Di chuyển số 0 đến cuối
• Thùng chứa nhiều nước nhất
• Loại bỏ các bản sao khỏi mảng được sắp xếp
• Cho dù một mảng là một tập hợp con của một mảng khác
• Hợp nhất hai mảng đã sắp xếp
• Tìm giao điểm của hai mảng đã sắp xếp
• Đếm số tam giác có thể
• Tìm bốn phần tử có tổng bằng một giá trị đã cho
• Bộ ba trong mảng có tổng bằng giá trị đã cho

Nếu bạn có bất kỳ ý tưởng/thắc mắc/nghi ngờ/phản hồi nào, vui lòng bình luận bên dưới hoặc viết thư cho chúng tôi tại [email protected] com. Thích học, Thích mã hóa, Thích thuật toán

Làm cách nào để tìm tất cả các cặp mảng số nguyên có tổng bằng số đã cho JavaScript?

Làm cách nào tôi có thể lấy các phần tử từ mảng có tổng bằng với giá trị đã cho?

Làm cách nào để tìm tất cả các cặp mảng số nguyên có tổng bằng một số đã cho trong Python?

Làm cách nào để tìm tất cả các cặp mảng số nguyên có tổng bằng số đã cho trong C?