Ký hiệu: TC - Time Complexity, SC - Space Complexity
Fact: trong thực tế, đa số sẽ ưu tiên trade Time complexity
hơn là Space
, vì ngày nay hạ tầng phần cứng đã tốt hơn rất nhiều so với ngày xưa, hơn có vài mb, thậm chí GB cũng chả là bao với các máy chủ hoặc hạ tầng Cloud!
Cách tiếp cận 1: Brute Force
Đây là cách đơn giản nhất, không phải nghĩ ngợi nhiều. Ta có 2 vòng lặp với array target. Ở vòng 1, ta đặt 1 biến tên là firstNum
với array[i]
, để rồi ở vòng 2, ta đặt 1 biến là secondNum
với array[j]
--> Cứ loop cho khi nào đến hết array, cặp này cộng lại = targetSum
thì return về [firstNum, secondNum]
, không có thì ta trả về empty array.
Về Complexity Analysis:
- TC: O(N^2), khi mà N là độ dài của input Array
- SC: 0(1)
function twoNumberSum(array, targetSum) {
cons arrayLength = array.length
for (int i = 0; i < arrayLength; i++) {
const firstNum = array[i];
for (int j = i + 1; j < arrayLength; j++) {
const secondNum = array[j]
const isPairNum = (firstNum + secondNum) === targetSum;
if (isPairNum) return [firstNum, secondNum)
}
}
return []
}
func TwoNumberSum(array []int, target int) []int {
arrayLength := len(array)
for i, firstNum := range array {
for j := i + 1; j < arrayLength; j++ {
secondNum := array[j]
if firstNum + secondNum == target {
return []int{firstNum, secondNum}
}
}
}
return []int{}
}
Cách tiếp cận 2: Sort + Dùng đầu cuối so sánh.
Mục tiêu của ta là TC giảm xuống còn O(N-LogN), còn SC sẽ là O(N-LogN hoặc N), tuỳ thuộc vào phần tính chất của dữ liệu và thuật toán sort ta chọn.
- Đầu tiên, để tránh mutate array, ta clone array + sort nó.
- Sẽ tạo 2 biến là
firstIdx
và lastIdx
, đại diện cho giá trị index của mảng đó
- Dùng
While loop
với điều kiện firstIdx < lastIdx
. Trong đó, có 1 biến currentSum
bằng với array[firstIdx] + array[lastIdx]
. Nếu currentSum
= targetSum
—> Return luôn. Còn không thì ta phải dựa vào currentSum < targetSum
, thì phải tăng firstIdx
lên 1, ngược lại thì giảm lastIdx
đi 1 - đó là lý do ta sort ở đầu tiên cho việc này.
function twoNumberSum(array, targetSum) {
const sortedArray = […array].sort()
let firstIdx = 0;
let lastIdx = sortedArray.length - 1;
while (firstIdx < lastIdx) {
const currentSum = sortedArray[firstIdx] + sortedArray[lastIdx];
if (currentSum === targetSum) return [sortedArray[firstIdx], sortedArray[lastIdx]];
if (currentSum < targetSum) {
firstIdx++;
} else {
lastIdx—;
}
}
return []
}
func TwoNumberSum(array []int, target int) []int {
sortedArray := sort.Ints(array)
firstIdx, lastIdx := 0, len(array) - 1
for firstIdx < lastIdx {
currentSum := sortedArray[firstIdx] + sortedArray[lastIdx]
if currentSum === target {
return []int{sortedArray...