Tìm 3 Phần Tử Có Tổng Bằng Key

Nguồn: Bài tập môn Cấu trúc dữ liệu & giải thuật Độ khó: Trung bình Vét cạn Sắp xếp Hai con trỏ

Đề bài

Tìm 3 phần tử có tổng bằng key

Cho mảng arr, tìm trong mảng arr có tồn tại 3 phần tử arr[i] + arr[j] + arr[k] = key, với key là giá trị cho trước. In giá trị arr[i], arr[j] và arr[k] ra màn hình.

1. Thiết kế giải thuật với ĐPT (độ phức tạp) về thời gian tùy ý.
2. Thiết kế giải thuật với ĐPT về thời gian là $O(n^2)$.

Đề gốc là bài thiết kế giải thuật (viết hàm), không có định dạng vào/ra. Để chạy thử và kiểm tra, mình quy ước: dòng đầu gồm $n$ và $key$; dòng thứ hai gồm $n$ số nguyên của mảng ($i, j, k$ là 3 vị trí khác nhau). Nếu tìm được thì in 3 giá trị trên một dòng (có nhiều bộ thì in bộ nào cũng được), không có thì in NO.

Ví dụ – input

6 24
12 3 4 1 6 9

Ví dụ – output (cách 2)

3 9 12

Lời mở đầu

Nay mình đi comment dạo thấy bài này thú vị nè: một bạn hỏi cách làm tối ưu cho câu b. Đây là bài kinh điển (hay gọi là bài 3SUM), rất hợp để anh em luyện cách đánh giá độ phức tạp và làm quen kỹ thuật hai con trỏ 😇.

Bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì link bài đây nhé:

Link nộp bài

Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.

Nộp bài trên CLUE OJ

Giải thích ví dụ: mảng $[12, 3, 4, 1, 6, 9]$ và $key = 24$. Ta có $12 + 3 + 9 = 24$ nên in ra 3 giá trị đó. Cách 1 duyệt theo thứ tự trong mảng nên in 12 3 9, còn cách 2 sắp xếp mảng trước nên in 3 9 12 – cả hai đều đúng.

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Cách 1 (câu a)Vét cạn 3 vòng lặp · O(N³)Cách 2 (câu b)Sắp xếp + hai con trỏ · O(N²)

Cách 1Vét cạn tất cả bộ 3 – O(N³)

Ở câu a đề cho thiết kế với độ phức tạp tuỳ ý, miễn giải quyết được vấn đề, thì cứ theo cách đơn giản nhất thôi: vét cạn xét tất cả các bộ 3 vị trí $i \lt j \lt k$. Gặp bộ 3 nào thoả mãn thì in ra và return true ngay, tức là kết thúc hàm tại đó luôn, khỏi mất công xét tiếp. Đến sau cùng không có bộ nào thoả thì return false.

Source code để các bạn tham khảo nếu làm theo hướng này:

#include <bits/stdc++.h>
using namespace std;

bool Check1(int *a, int n, int key){
    for(int i = 0; i < n; ++i){
        for(int j = i + 1; j < n; ++j){
            for(int k = j + 1; k < n; ++k){
                if((long long)a[i] + a[j] + a[k] == key){
                    cout << a[i] << " " << a[j] << " " << a[k] << endl;
                    return true;
                }
            }
        }
    }
    return false;
}

int main(){
    int n, key;
    cin >> n >> key;
    int *a = new int[n];
    for(int i = 0; i < n; ++i){
        cin >> a[i];
    }
    if(!Check1(a, n, key)){
        cout << "NO" << endl;
    }
    delete[] a;
    return 0;
}

def check1(a, n, key):
    for i in range(n):
        for j in range(i + 1, n):
            for k in range(j + 1, n):
                if a[i] + a[j] + a[k] == key:
                    print(a[i], a[j], a[k])
                    return True
    return False


data = list(map(int, open(0).read().split()))
n, key = data[0], data[1]
a = data[2:2 + n]
if not check1(a, n, key):
    print("NO")

Đánh giá độ phức tạp của cách làm này:

• Thời gian: quá đơn giản để nhìn ra, 3 vòng lặp lồng nhau, trường hợp xấu nhất mỗi vòng chạy đủ $N$ lần ⇒ $O(N^3)$ với $N$ là số phần tử của mảng.
• Không gian: $O(N)$ do xử lý trên mảng có $N$ phần tử.

Không gian$O(N)$

Thời gian$O(N^3)$

Nên để i < n hay i < n - 2?

Cách này đơn giản quá nên mình nói thêm một chút để anh em có thêm kiến thức. Với 3 vòng lặp lồng nhau thế này sẽ có anh em để điều kiện i < n - 2, j < n - 1, k < n. Để vậy cũng ok, vẫn đúng và về lý thuyết vẫn là $O(N^3)$. Tuy nhiên mình khuyên cứ để i < n, j < n, k < n cho gọn mà tính kỹ ra còn tốt hơn: khi để i < n - 2 thì tuy không phải lặp dư 2 lần, nhưng đổi lại cứ mỗi lần so sánh điều kiện vòng lặp là lại phải làm thêm phép tính n - 2. Giả sử $n$ là 1 triệu thì phải làm thêm gần 1 triệu phép trừ, trong khi để i < n thì chỉ lặp dư 2 lần chẳng làm gì mà không phải liên tục tính phép trừ ^^. Tương tự với vòng lặp j nhé! (Thực tế trình biên dịch hiện đại thường tự tối ưu chỗ này, nhưng thói quen viết gọn vẫn tốt.)

Cách 2Sắp xếp + hai con trỏ – O(N²)

Ở câu b đề ràng buộc độ phức tạp phải là $O(N^2)$ ⇒ không làm 3 vòng lặp lồng nhau được nữa mà phải tối ưu hơn. $N^2$ thì anh em hiểu là tối đa 2 vòng lặp lồng nhau, mỗi vòng chạy tối đa $N$ lần. Để làm được, ta kết hợp kỹ thuật sort (sắp xếp) và two pointers (hai con trỏ):

1. Sắp xếp mảng tăng dần. Dùng thuật tối ưu $O(N \log N)$ thì tốt, còn dùng thuật tệ nhất $O(N^2)$ (như Bubble Sort) thì vẫn đúng yêu cầu đề nhé.
2. Duyệt i lần lượt từng phần tử bắt đầu từ thằng nhỏ nhất. Với mỗi a[i], ta tìm 2 thằng còn lại bằng hai con trỏ: left = i + 1 (ngay sau i) và right = n - 1 (cuối dãy).
3. Trong khi left < right: tính sum = a[i] + a[left] + a[right].
   • sum > key ⇒ tổng đang dư, giảm right xuống để lấy số nhỏ hơn.
   • sum < key ⇒ tổng đang thiếu, tăng left lên để lấy số lớn hơn.
   • sum == key ⇒ tìm thấy, in ra và return true.
4. Khi left >= right mà chưa tìm được thì với a[i] hiện tại không có cặp nào hợp lệ ⇒ xét i tiếp theo. Hết mọi i vẫn không có ⇒ return false.

Vì sao dời con trỏ như vậy mà không bỏ sót?

Mảng đang tăng dần. Nếu sum > key thì ghép a[right] với bất kỳ phần tử nào từ left trở đi cũng chỉ càng lớn hơn ⇒ a[right] không thể nằm trong đáp án, bỏ nó đi (right--). Ngược lại nếu sum < key thì a[left] ghép với bất kỳ phần tử nào đến right cũng chỉ càng nhỏ hơn ⇒ bỏ a[left] (left++). Nếu mảng sắp giảm dần thì làm ngược lại: sum > key thì tăng left, sum < key thì giảm right. Chỗ này anh em suy nghĩ một tí là hiểu hen.

Dừng sớm cho nhanh

Trong code mình có thêm bước: nếu a[i] không âm mà đã > key thì dừng luôn, vì càng về sau các số càng lớn, không thể có bộ 3 nào có tổng bằng key nữa (vì sao phải có điều kiện "không âm" thì xem hộp bên dưới).

Cẩn thận với số âm và tràn số

Bản code mình gõ trên điện thoại ngày trước chỉ ghi if(a[i] > key) return false; – điều này chỉ đúng khi mảng không có số âm. Nếu có số âm thì sai, ví dụ mảng $[-3, -1, -1]$ với $key = -5$: $a[0] = -3 \gt -5$ nên dừng và trả về false, trong khi $-3 + (-1) + (-1) = -5$. Vì vậy mình sửa điều kiện thành a[i] >= 0 && a[i] > key: khi a[i] >= 0 thì các số phía sau cũng $\ge a[i] \ge 0$, tổng 3 số $\ge a[i] \gt key$ ⇒ dừng mới chắc chắn đúng. Ngoài ra mình tính tổng bằng long long để không bị tràn khi các phần tử lớn cỡ $10^9$ (cách 1 cũng vậy).

Minh hoạ hai con trỏ

Em nhập mảng và $key$ rồi bấm Tiếp để xem: mảng được sắp xếp, rồi với mỗi i hai con trỏ L, R tiến lại gần nhau:

Mảng key

Ví dụ nhanh:

Source code để các bạn tham khảo nếu làm theo hướng này:

#include <bits/stdc++.h>
using namespace std;

bool Check2(int *a, int n, int key){
    sort(a, a + n);
    for(int i = 0; i < n; ++i){
        if(a[i] >= 0 && a[i] > key){
            return false;
        }
        int left = i + 1;
        int right = n - 1;
        while(left < right){
            long long sum = (long long)a[i] + a[left] + a[right];
            if(sum > key){
                right--;
            }
            else if(sum < key){
                left++;
            }
            else{
                cout << a[i] << " " << a[left] << " " << a[right] << endl;
                return true;
            }
        }
    }
    return false;
}

int main(){
    int n, key;
    cin >> n >> key;
    int *a = new int[n];
    for(int i = 0; i < n; ++i){
        cin >> a[i];
    }
    if(!Check2(a, n, key)){
        cout << "NO" << endl;
    }
    delete[] a;
    return 0;
}

import sys


def check2(a, n, key):
    a.sort()
    for i in range(n):
        if a[i] >= 0 and a[i] > key:
            return False
        left = i + 1
        right = n - 1
        while left < right:
            s = a[i] + a[left] + a[right]
            if s > key:
                right -= 1
            elif s < key:
                left += 1
            else:
                print(a[i], a[left], a[right])
                return True
    return False


data = list(map(int, sys.stdin.read().split()))
n, key = data[0], data[1]
a = data[2:2 + n]
if not check2(a, n, key):
    print("NO")

C++▶ Chạy tay từng dòng codeSắp xếp tăng dần, với mỗi i dùng hai con trỏ left/right tìm cặp còn lại.

Dữ liệu vào (stdin) – sửa thoải mái6 24 12 3 4 1 6 9

Dữ liệu mẫu:

1#include <bits/stdc++.h>

2using namespace std;

3

4bool Check2(int *a, int n, int key){

5 sort(a, a + n);

6 for(int i = 0; i < n; ++i){

7 if(a[i] >= 0 && a[i] > key){

8 return false;

9 }

10 int left = i + 1;

11 int right = n - 1;

12 while(left < right){

13 long long sum = (long long)a[i] + a[left] + a[right];

14 if(sum > key){

15 right--;

16 }

17 else if(sum < key){

18 left++;

19 }

20 else{

21 cout << a[i] << " " << a[left] << " " << a[right] << endl;

22 return true;

23 }

24 }

25 }

26 return false;

27}

28

29int main(){

30 int n, key;

31 cin >> n >> key;

32 int *a = new int[n];

33 for(int i = 0; i < n; ++i){

34 cin >> a[i];

35 }

36 if(!Check2(a, n, key)){

37 cout << "NO" << endl;

38 }

39 delete[] a;

40 return 0;

41}

ChậmVừaNhanhRất nhanh

Đánh giá độ phức tạp của cách làm này:

• Thời gian: bước sắp xếp mình dùng hàm sort trong thư viện algorithm nên là $O(N \log N)$ (tự code Bubble Sort $O(N^2)$ thì vẫn thoả đề). Phần hai con trỏ: trường hợp xấu nhất (không tìm thấy) vòng for i chạy hết $N$ lần, mỗi lần vòng while xét hết các phần tử phía sau i (mỗi bước left tăng hoặc right giảm nên không quá $N$ bước) ⇒ $O(N^2)$. Tổng $O(N \log N + N^2)$, theo quy tắc cộng Big-O lấy thằng lớn nhất ⇒ $O(N^2)$, đúng yêu cầu đề.
• Không gian: $O(N)$ do xử lý trên mảng có $N$ phần tử.

Không gian$O(N)$

Thời gian$O(N^2)$

Dùng map được không?

Có bạn hỏi dùng map với 2 vòng lặp được không – được nha: cố định i, duyệt j phía sau và tra xem đã gặp giá trị key - a[i] - a[j] trong đoạn giữa i và j chưa (dùng set/unordered_set làm mới cho mỗi i). Với unordered_set thì trung bình $O(N^2)$, còn map/set thì thành $O(N^2 \log N)$ và tốn thêm bộ nhớ. Cách hai con trỏ ở trên gọn và nhanh hơn.

Ghi chú của mình: code C++ và Python của cả 2 cách đã được kiểm tra với 600 bộ test ngẫu nhiên (có số âm, có phần tử trùng, có bộ không có đáp án), mỗi output được kiểm tra bằng code vét cạn: in NO thì đúng là không có bộ 3 nào, còn in 3 số thì đúng là lấy từ mảng và có tổng bằng key – khớp hết. Với $n = 5000$ và không có đáp án: cách 2 bản C++ chạy khoảng 0.03 giây, bản Python khoảng 1.7 giây; cách 1 bản C++ mất khoảng 15–18 giây ⇒ thấy rõ khác biệt giữa $O(N^3)$ và $O(N^2)$.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇