استراتيجية التحسين بالتجزئة

Go

/* الطريقة 1: التعداد بالقوة الغاشمة */
func twoSumBruteForce(nums []int, target int) []int {
	size := len(nums)
	// حلقتان متداخلتان، التعقيد الزمني هو O(n^2)
	for i := 0; i < size-1; i++ {
		for j := i + 1; j < size; j++ {
			if nums[i]+nums[j] == target {
				return []int{i, j}
			}
		}
	}
	return nil
}

TypeScript

/* الطريقة 1: التعداد بالقوة الغاشمة */
function twoSumBruteForce(nums: number[], target: number): number[] {
    const n = nums.length;
    // حلقتان متداخلتان، التعقيد الزمني هو O(n^2)
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            if (nums[i] + nums[j] === target) {
                return [i, j];
            }
        }
    }
    return [];
}

Go

/* الطريقة 2: جدول تجزئة مساعد */
func twoSumHashTable(nums []int, target int) []int {
	// جدول تجزئة مساعد، التعقيد المكاني هو O(n)
	hashTable := map[int]int{}
	// حلقة واحدة، التعقيد الزمني هو O(n)
	for idx, val := range nums {
		if preIdx, ok := hashTable[target-val]; ok {
			return []int{preIdx, idx}
		}
		hashTable[val] = idx
	}
	return nil
}

TypeScript

/* الطريقة 2: جدول تجزئة مساعد */
function twoSumHashTable(nums: number[], target: number): number[] {
    // جدول تجزئة مساعد، التعقيد المكاني هو O(n)
    let m: Map<number, number> = new Map();
    // حلقة واحدة، التعقيد الزمني هو O(n)
    for (let i = 0; i < nums.length; i++) {
        let index = m.get(target - nums[i]);
        if (index !== undefined) {
            return [index, i];
        } else {
            m.set(nums[i], i);
        }
    }
    return [];
}