Giải bài toán Two Number Sum?

Vấn đề đặt ra: Cho 1 array với các số integer khác biệt và 1 số đại diện cho target sum. Hãy implement 1 function mà bạn phải tim ra một cặp số trong array mà cộng lại = số target sum kia. Nếu tồn tại cặp số đó thì trả về, không thì trả về một empty array.

VD Input: twoNumberSum([3, 5, -4, 10, 11, 1, -1, 4], 10) --> [11, -1]

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.

1. Đầu tiên, để tránh mutate array, ta clone array + sort nó.
2. Sẽ tạo 2 biến là firstIdx và lastIdx, đại diện cho giá trị index của mảng đó
3. 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, lastI...