Mảng (Array)

Array là gì?

Mảng (Array) là cấu trúc dữ liệu lưu trữ các phần tử liên tiếp trong bộ nhớ, cho phép truy cập nhanh bằng chỉ số (index).

💡

Array là cấu trúc dữ liệu cơ bản nhất. Trong hầu hết ngôn ngữ, mảng có truy cập O(1) theo index!

Khai báo và khởi tạo

Python


# Python dùng List (dynamic array)
arr = [10, 20, 30, 40, 50]
#      0   1   2   3   4   ← index
 
# Truy cập
print(arr[0])   # 10
print(arr[-1])  # 50 (phần tử cuối)
 
# Cập nhật
arr[2] = 99

Kotlin


// Kotlin dùng List và MutableList
val arr = listOf(10, 20, 30, 40, 50)  // Immutable
val mutableArr = mutableListOf(10, 20, 30)  // Mutable
 
// Truy cập
println(arr[0])   // 10
println(arr.last())  // 50
 
// Cập nhật (chỉ với MutableList)
mutableArr[2] = 99

Dart


// Dart dùng List
List<int> arr = [10, 20, 30, 40, 50];
 
// Truy cập
print(arr[0]);     // 10
print(arr.last);   // 50
 
// Cập nhật
arr[2] = 99;

Swift


// Swift dùng Array
var arr = [10, 20, 30, 40, 50]
 
// Truy cập
print(arr[0])     // 10
print(arr.last!)  // 50
 
// Cập nhật
arr[2] = 99

Java


// Java dùng array hoặc ArrayList
int[] arr = {10, 20, 30, 40, 50};
ArrayList<Integer> list = new ArrayList<>(Arrays.asList(10, 20, 30));
 
// Truy cập
System.out.println(arr[0]);  // 10
System.out.println(list.get(0));
 
// Cập nhật
arr[2] = 99;
list.set(2, 99);

Các thao tác cơ bản

Thêm phần tử

Python


arr = [10, 20, 30]
 
arr.append(40)      # Thêm cuối: O(1)
arr.insert(1, 15)   # Thêm vào vị trí: O(n)
arr.extend([50, 60])  # Thêm nhiều phần tử

Kotlin


val arr = mutableListOf(10, 20, 30)
 
arr.add(40)          // Thêm cuối: O(1)
arr.add(1, 15)       // Thêm vào vị trí: O(n)
arr.addAll(listOf(50, 60))  // Thêm nhiều

Dart


List<int> arr = [10, 20, 30];
 
arr.add(40);           // Thêm cuối: O(1)
arr.insert(1, 15);     // Thêm vào vị trí: O(n)
arr.addAll([50, 60]);  // Thêm nhiều

Swift


var arr = [10, 20, 30]
 
arr.append(40)           // Thêm cuối: O(1)
arr.insert(15, at: 1)    // Thêm vào vị trí: O(n)
arr.append(contentsOf: [50, 60])  // Thêm nhiều

Java


ArrayList<Integer> arr = new ArrayList<>(Arrays.asList(10, 20, 30));
 
arr.add(40);           // Thêm cuối: O(1)
arr.add(1, 15);        // Thêm vào vị trí: O(n)
arr.addAll(Arrays.asList(50, 60));

Xóa phần tử

Python


arr = [10, 20, 30, 40, 50]
 
arr.remove(30)    # Xóa theo giá trị: O(n)
del arr[1]        # Xóa theo index: O(n)
last = arr.pop()  # Xóa và trả về cuối: O(1)

Kotlin


val arr = mutableListOf(10, 20, 30, 40, 50)
 
arr.remove(30)        // Xóa theo giá trị: O(n)
arr.removeAt(1)       // Xóa theo index: O(n)
val last = arr.removeLast()  // Xóa cuối: O(1)

Dart


List<int> arr = [10, 20, 30, 40, 50];
 
arr.remove(30);       // Xóa theo giá trị: O(n)
arr.removeAt(1);      // Xóa theo index: O(n)
int last = arr.removeLast();  // Xóa cuối: O(1)

Swift


var arr = [10, 20, 30, 40, 50]
 
arr.removeAll { $0 == 30 }  // Xóa theo giá trị
arr.remove(at: 1)           // Xóa theo index: O(n)
let last = arr.removeLast() // Xóa cuối: O(1)

Java


ArrayList<Integer> arr = new ArrayList<>(Arrays.asList(10, 20, 30, 40, 50));
 
arr.remove(Integer.valueOf(30));  // Xóa theo giá trị
arr.remove(1);                     // Xóa theo index: O(n)
int last = arr.remove(arr.size() - 1);  // Xóa cuối

Độ phức tạp

Thao tác	Độ phức tạp
Truy cập `arr[i]`	O(1)
Thêm/xóa cuối	O(1)
Thêm/xóa đầu hoặc giữa	O(n)
Tìm kiếm	O(n)

Kỹ thuật Two Pointers

Python


def reverse_array(arr):
    """Đảo ngược mảng in-place"""
    left, right = 0, len(arr) - 1
    while left < right:
        arr[left], arr[right] = arr[right], arr[left]
        left += 1
        right -= 1
    return arr

Kotlin


fun reverseArray(arr: MutableList<Int>): List<Int> {
    var left = 0
    var right = arr.size - 1
    while (left < right) {
        val temp = arr[left]
        arr[left] = arr[right]
        arr[right] = temp
        left++; right--
    }
    return arr
}

Dart


List<int> reverseArray(List<int> arr) {
  int left = 0, right = arr.length - 1;
  while (left < right) {
    int temp = arr[left];
    arr[left] = arr[right];
    arr[right] = temp;
    left++; right--;
  }
  return arr;
}

Swift


func reverseArray(_ arr: inout [Int]) {
    var left = 0, right = arr.count - 1
    while left < right {
        arr.swapAt(left, right)
        left += 1; right -= 1
    }
}

Java


void reverseArray(int[] arr) {
    int left = 0, right = arr.length - 1;
    while (left < right) {
        int temp = arr[left];
        arr[left] = arr[right];
        arr[right] = temp;
        left++; right--;
    }
}

Kỹ thuật Sliding Window

Python


def max_sum_subarray(arr, k):
    """Tìm tổng lớn nhất của k phần tử liên tiếp"""
    n = len(arr)
    window_sum = sum(arr[:k])
    max_sum = window_sum
    
    for i in range(k, n):
        window_sum += arr[i] - arr[i - k]
        max_sum = max(max_sum, window_sum)
    
    return max_sum

Kotlin


fun maxSumSubarray(arr: List<Int>, k: Int): Int {
    var windowSum = arr.take(k).sum()
    var maxSum = windowSum
    
    for (i in k until arr.size) {
        windowSum += arr[i] - arr[i - k]
        maxSum = maxOf(maxSum, windowSum)
    }
    return maxSum
}

Dart


int maxSumSubarray(List<int> arr, int k) {
  int windowSum = arr.take(k).reduce((a, b) => a + b);
  int maxSum = windowSum;
  
  for (int i = k; i < arr.length; i++) {
    windowSum += arr[i] - arr[i - k];
    if (windowSum > maxSum) maxSum = windowSum;
  }
  return maxSum;
}

Swift


func maxSumSubarray(_ arr: [Int], _ k: Int) -> Int {
    var windowSum = arr[0..<k].reduce(0, +)
    var maxSum = windowSum
    
    for i in k..<arr.count {
        windowSum += arr[i] - arr[i - k]
        maxSum = max(maxSum, windowSum)
    }
    return maxSum
}

Java


int maxSumSubarray(int[] arr, int k) {
    int windowSum = 0;
    for (int i = 0; i < k; i++) windowSum += arr[i];
    int maxSum = windowSum;
    
    for (int i = k; i < arr.length; i++) {
        windowSum += arr[i] - arr[i - k];
        maxSum = Math.max(maxSum, windowSum);
    }
    return maxSum;
}

Two Sum Problem

Python


def two_sum(arr, target):
    """Tìm 2 số có tổng bằng target"""
    seen = {}
    for i, num in enumerate(arr):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i
    return []

Kotlin


fun twoSum(arr: List<Int>, target: Int): List<Int> {
    val seen = mutableMapOf<Int, Int>()
    for ((i, num) in arr.withIndex()) {
        val complement = target - num
        if (complement in seen) {
            return listOf(seen[complement]!!, i)
        }
        seen[num] = i
    }
    return emptyList()
}

Dart


List<int> twoSum(List<int> arr, int target) {
  Map<int, int> seen = {};
  for (int i = 0; i < arr.length; i++) {
    int complement = target - arr[i];
    if (seen.containsKey(complement)) {
      return [seen[complement]!, i];
    }
    seen[arr[i]] = i;
  }
  return [];
}

Swift


func twoSum(_ arr: [Int], _ target: Int) -> [Int] {
    var seen = [Int: Int]()
    for (i, num) in arr.enumerated() {
        let complement = target - num
        if let j = seen[complement] {
            return [j, i]
        }
        seen[num] = i
    }
    return []
}

Java


int[] twoSum(int[] arr, int target) {
    Map<Integer, Integer> seen = new HashMap<>();
    for (int i = 0; i < arr.length; i++) {
        int complement = target - arr[i];
        if (seen.containsKey(complement)) {
            return new int[]{seen.get(complement), i};
        }
        seen.put(arr[i], i);
    }
    return new int[]{};
}

Tiếp theo: Danh sách liên kết (Linked List)