- vừa được xem lúc

Two Sum – Bài toán khởi đầu nhưng không hề tầm thường

0 0 4

Người đăng: Nguyễn Ánh Dung

Theo Viblo Asia

Mô tả bài toán

Cho một mảng số nguyên nums và một số nguyên target, hãy trả về chỉ số của hai phần tử trong mảng sao cho tổng của chúng bằng target.

Giả định: Mỗi input chỉ có đúng một lời giải duy nhất, và không được dùng lại cùng một phần tử hai lần.

Ví dụ:

Input: nums = [2, 7, 11, 15], target = 9 Output: [0, 1] Vì nums[0] + nums[1] = 2 + 7 = 9

Tư duy & các cách giải bài toán

Cách 1: Brute Force – Duyệt 2 vòng for Ý tưởng: Duyệt từng cặp số trong mảng để kiểm tra xem tổng có bằng target không.

def twoSum(nums, target): n = len(nums) for i in range(n): for j in range(i + 1, n): if nums[i] + nums[j] == target: return [i, j]

Độ phức tạp: O(n^2) thời gian, O(1) bộ nhớ

Nhược điểm: Chậm khi mảng lớn.

Cách 2: Hashmap – Lưu phần tử đã duyệt

Ý tưởng: Duyệt qua mảng 1 lần, lưu lại số đã gặp và chỉ số của nó. Tại mỗi bước, ta kiểm tra phần còn thiếu (target - nums[i]) đã xuất hiện chưa.

def twoSum(nums, target): seen = {} for i, num in enumerate(nums): remain = target - num if remain in seen: return [seen[remain], i] seen[num] = i

Độ phức tạp: O(n) thời gian, O(n) bộ nhớ

Ưu điểm: Nhanh và hiệu quả nhất cho bài toán này.

Cách hoạt động: giống như nhớ lại các số cũ và tìm nửa còn lại.

Một vài lưu ý khi làm bài này

Không được trùng chỉ số, nên cần kiểm tra thứ tự đúng.

Hashmap là dict trong Python, hoạt động rất nhanh.

Khi bị yêu cầu trả ra giá trị chứ không phải chỉ số, cần thay đổi logic một chút.

Các biến thể tương tự để luyện tập

Two Sum II - Input array is sorted → Dùng kỹ thuật two pointers

3Sum, 4Sum → Mở rộng lên nhiều phần tử, kết hợp sắp xếp và 2-pointer.

Subarray Sum Equals K → Cũng là tổng nhưng với mảng con liên tiếp.

Kết luận

Mặc dù đơn giản, bài Two Sum giúp hiểu được cách tối ưu hóa từ brute-force lên hashmap, đồng thời làm quen với cách xử lý bài toán có điều kiện, kiểm tra ngược lại từ dữ liệu đã có.

Bình luận

Bài viết tương tự

- vừa được xem lúc

Thuật toán quay lui (Backtracking)

Quay lui là một kĩ thuật thiết kế giải thuật dựa trên đệ quy. Ý tưởng của quay lui là tìm lời giải từng bước, mỗi bước chọn một trong số các lựa chọn khả dĩ và đệ quy.

0 0 60

- vừa được xem lúc

Các thuật toán cơ bản trong AI - Phân biệt Best First Search và Uniform Cost Search (UCS)

Nếu bạn từng đọc các thuật toán trong AI (Artificial Intelligence - Trí tuệ nhân tạo), rất có thể bạn từng nghe qua về các thuật toán tìm kiếm cơ bản: UCS (thuộc chiến lược tìm kiếm mù) và Best First Search (thuộc chiến lược tìm kiếm kinh nghiệm). Khác nhau rõ từ khâu phân loại rồi, thế nhưng hai th

0 0 184

- vừa được xem lúc

Sử dụng vector trong lập trình C++ - giải bài toán lập trình muôn thủa

Chào buổi tối mọi người, hôm nay lang thang trên mạng bắt gặp bài toán quen thuộc một thời của quãng đường sinh viên IT. Đấy chính là câu số 1 trong đề thi dưới đây:.

0 0 69

- vừa được xem lúc

MÔ PHỎNG THUẬT TOÁN VƯƠNG HẠO TRONG PROLOG

. 1. Các luật suy diễn trong thuật toán Vương Hạo. Luật 1: Chuyển vế các giả thuyết và kết luận ở dạng phủ định. Ví dụ: p v q, !(r ^ s), !q, p v r -> s, !p <=> p v q, p v r, p -> s, r ^ s, q.

0 0 102

- vừa được xem lúc

A* Search Algorithm

What is A* Search Algorithm. How it works. . Explanation.

0 0 64

- vừa được xem lúc

Python: Jump Search

Search là một từ khóa khá là quen thuộc đối với chúng ta. Hiểu theo đúng nghĩa đen của nó chính là "Tìm kiếm".

0 0 61