תיאור השאלה
Given an array nums of n integers and an integer target, return all unique quadruplets [nums[a], nums[b], nums[c], nums[d]] whose sum equals target.
- The indices
a,b,canddare distinct. - The answer must not contain duplicate quadruplets.
איך פותרים?
ממיינים את המערך, מקבעים שני מספרים בשתי לולאות, ואת שני האחרונים מחפשים עם שני מצביעים משני הקצוות. מדלגים על ערכים חוזרים כדי לא לקבל רביעיות כפולות. סיבוכיות: O(n³).
פתרון קוד
JavaScript
Python
function fourSum(nums, target) {
nums.sort((a, b) => a - b);
const result = [];
const n = nums.length;
for (let i = 0; i < n - 3; i++) {
if (i > 0 && nums[i] === nums[i - 1]) continue;
for (let j = i + 1; j < n - 2; j++) {
if (j > i + 1 && nums[j] === nums[j - 1]) continue;
let left = j + 1;
let right = n - 1;
while (left < right) {
const sum = nums[i] + nums[j] + nums[left] + nums[right];
if (sum === target) {
result.push([nums[i], nums[j], nums[left], nums[right]]);
left++;
right--;
while (left < right && nums[left] === nums[left - 1]) left++;
while (left < right && nums[right] === nums[right + 1]) right--;
} else if (sum < target) {
left++;
} else {
right--;
}
}
}
}
return result;
}
לעבור את ראיון העבודה הבא שלך בהצלחה
קורס דיגיטלי מקיף עם +25 שיעורים מעשיים, כשעתיים של וידאו, וליווי של מראיין בכיר.